Linked List Cycle II 103

Question

Given a linked list, return the node where the cycle begins.

If there is no cycle, return null.

Example

Given -21->10->4->5, tail connects to node index 1，return 10

Challenge

Follow up:

Can you solve it without using extra space?

Solution

1. 先用快慢指针判断是不是存在环

2. 当slow和fast第一次相遇时，将slow放回Start处，fast向下移动一步，两个指针再一起移动，直到再次相遇，就是交点

为什么slow放回start处，fast要向下移动一位：slow和fast第一次相当于从head之前的一个dummy node一起出发，slow移动一步到head，fast移动两步到head.next，所以第一次相遇之后，相当于要将slow放回dummy，然后slow和fast一起移动（一步之后slow到达head，fast到达fast.next）。

证明：

现在有两个指针，第一个指针，每走一次走一步，第二个指针每走一次走两步，如果他们走了t次之后相遇在K点

那么指针一走的路是 t = X + nY + K ①

指针二走的路是 2t = X + mY+ K ② m,n为未知数

把等式一代入到等式二中, 有

2X + 2nY + 2K = X + mY+ K

X + (2n-m)Y + K = 0;

X + K = (m - 2n)Y

这就清晰了，X和K的关系是基于Y互补的。等于说，两个指针相遇以后，再往下走X步就回到Cycle的起点了。

代码如下：

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: The node where the cycle begins. 
     *           if there is no cycle, return null
     */
    public ListNode detectCycle(ListNode head) {  
        // write your code here
        if(head == null || head.next == null){
            return null;
        }

        ListNode slow = head;
        ListNode fast = head.next;

        while(slow != fast){
            if(fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }else{
                return null;
            }
        }

        slow = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }
}