【解题报告】【lintcode103】Linked List Cycle II

题意

给出一个链表，可能会有环（从某一点开始，经过一段之后又回到这个点），找出这个环的开始点 使用O(n)的复杂度解决

解答

我们可以设置两个指针，一个每次前进一步，一个每次前进两步 那么，如果有环，这两个指针必定在环里某一个点相遇，这时候 假设环外到环开始点的路程为a 假设慢指针在环内走了b 环剩下的部分距离为c 那么，我们可以得到 (a+(b+c)+b)/2 = a + b 左边是快指针走过的距离除以速度，右边是慢指针距离除以速度 化简之后可以得到 a = c 所以，从相遇点开始，把慢指针放到链表开头，然后和快指针一起以1的速度移动，再次相遇的地方就是环的开始点了 如下图

代码

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) {  
        if(head == null)return null;
       ListNode node1,node2;
       node1 = head;
       node2 = head;
        for(;;){
            node1 = node1.next;
            if(node1 == null)return null;
            if(node2 == null)return null;
            node2 = node2.next;
            if(node2 == null)return null;
            node2 = node2.next;
            if(node1 == node2)
            break;
        }
            node1 = head;
        for(;;){
            if(node1 == node2)
            break;
            node1 =node1.next;
            node2 = node2.next;
        }
        return node1;
    }
}