给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
/**
*思路：
1.先新建两个指针分别指向头部
2.慢指针p1每次走一步，快指针p2每次走两步
3.如果存在环，那么快指针跟慢指针一定会相遇在环的某个点P
4.假设起点到入环点的距离为D，入环点到第一次相遇点的距离为S1，环的剩余长度为S2，
因为环走一圈会回到原点
5.这样可计算相遇时 P1走的长度为 D + S1,P2走的长度为 D + S1 + n(S1 + S2)
6.由2可知P2走的距离是P1的两倍，所以得到 2（D + S1） = D + S1 + n(S1 + S2)
化简可得D = (n - 1)(S1 + S2) + S2;从移动距离来讲，S1+S2=0,所以D = S2;
7.所以当p1和p2相遇后，将p2放回原点，p1和p2按1步走，再次相遇的点就是入环点
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null){
return null;
}
if(head.next.next == head)
return head;
ListNode p1 = head;
ListNode p2 = head;
//是否相遇
boolean meet = false;
while( p2.next != null && p2.next.next != null){
if(!meet){
p1= p1.next;
p2 = p2.next.next;
}else{
p1= p1.next;
p2 = p2.next;
}
//第一次相遇,要把快指针p2放回起点
if(p1 == p2 && !meet ){
meet = true;
p2 = head;
}
//第二次相遇
else if(p1 == p2 && meet){
return p1;
}
}
return null;
}
}
