Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

Solution:

两个游标（p1，p2）从头节点开始遍历链表，p1每次走一步，p2每次走两步，如果有环，那么p2始终会在环上与p1相遇。

假设链表长度为n，环开始的节点为到头节点有k步，p1和p2在距离环开始的节点m步的地方相遇（按顺时针），假设相遇节点到环开始的节点d步（按顺时针），那么p1走的路程为k+m，p2走的路程为k+m+d+m，显然p2走的路程为p1的2倍，于是2(k+m)=k+2m+d，于是我们推出d=k。

p1和p2相遇后，把p1只想头节点，然后p1,p2都一次走一步，走了k步后p1 p2相遇，该节点就是环开始的节点。

Time complexity is O(n), constant space.

/**
 * 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 slow = head;
        ListNode fast = head;

        //找到第一次相遇点
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) break;  //相遇
        }
        
        //检查是否因为有环退出或是因为碰到null而退出
        if(fast == null || fast.next == null)
            return null;
        
        // 把慢指针移到链表头，然后保持快慢指针同样的速度移动  
        // 再次相遇时即为环的入口 
        slow = head;
        while(fast != slow) {
            slow = slow.next;
            fast = fast.next;
        }
        
        //快慢指针都指向入口
        return fast;
    }
}