環(huán)的探測： 通過一個slow和fast指針，如果他們能夠相遇瘾敢，就能證明有環(huán)拍冠。
如何確定環(huán)的入口？
展開的環(huán)
假定一個環(huán)展開如上圖簇抵，其中y表明環(huán)的前y個點庆杜， N表示環(huán)的部分。通過將環(huán)展開碟摆，我們得到上圖的形式晃财。
現(xiàn)在我們可以假定在fast指針和slow指針相遇時，處于N的第r個典蜕，則可以證明：2r + y = r + XN, 可得r = XN - y其中X是整數(shù)断盛， 0<=r<N, 可知 1 + y/N > X > y/N
則此時在相遇點將N分成兩部分：r 和 N - r罗洗，假定一個指針將后面的N - r部分走完，另一個指針從頭部重新走钢猛，則頭部指針到環(huán)的入口剩余y - N + r = (X-1)N, 此時另外一個指針恰好位于環(huán)的入口伙菜。它們距離環(huán)都是N的整數(shù)倍，所以它們只需要按步長為1進(jìn)行遞增命迈，最終第一個相遇的位置一定是環(huán)的入口贩绕。
代碼如下：
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head==null){
return null;
}
ListNode fast = head;
ListNode slow = head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(slow == fast){
fast = head;
while(fast!=slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}
}
