[LintCode] 103 Linked List Cycle II 解题报告

Description
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?



思路
先用Linked List Cycle这题的解题思路来找有没有环。
如果有环，我们从快慢指针重合的位置，以及从链表的头，开始每次走一步，一直走到这两个指针重合，就是我们要找的环的入口。
用个不严格的推导：

假设上面这个例子，slow指针从1走到3要走x，从3走到和fast指针重合要再走y，这个环的长度是r。
假设fast多走1圈就可以和slow重合，那么重合的时候slow走了x + y，fast走了x + r + y。
我们知道fast走了slow的两倍，也就是2x + 2y。
所以2x + 2y = x + y + r
==> r - y = x
从slow和fast的重合点，再走到环的入口，我们知道需要r - y，也就是上面结论里的x。这说明slow和fast的重合点到环的距离，和链表头到环的距离是一样的。


Code

/**
 * 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;
        
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                while (head != slow) {
                    head = head.next;
                    slow = slow.next;
                }
                return head;
            }
        }
        
        return null;
    }
}