链表的环和入口

环的探测： 通过一个slow和fast指针，如果他们能够相遇，就能证明有环。
如何确定环的入口？

展开的环

假定一个环展开如上图，其中y表明环的前y个点， N表示环的部分。通过将环展开，我们得到上图的形式。

现在我们可以假定在fast指针和slow指针相遇时，处于N的第r个，则可以证明：2r + y = r + XN, 可得r = XN - y其中X是整数， 0<=r<N, 可知 1 + y/N > X > y/N
则此时在相遇点将N分成两部分：r 和 N - r，假定一个指针将后面的N - r部分走完，另一个指针从头部重新走，则头部指针到环的入口剩余y - N + r = (X-1)N, 此时另外一个指针恰好位于环的入口。它们距离环都是N的整数倍，所以它们只需要按步长为1进行递增，最终第一个相遇的位置一定是环的入口。

代码如下：

/**
 * 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;
    }
}