LeetCode 142. Linked List Cycle II

题目：[leetcode-142]

思路

寻找环的入口，需要做如下的数学证明。先给出示意图如下：

做如下假设：

• 设直线段的端点为 X点
• 环的入口点为 Y点
• 快慢指针相遇的点为 Z点
• 其中，有 XY−→−=l,YZ−→−=r0ZY−→−=c,

当快慢指针相遇时，有下面的式子：

dlow=l+r0(1)

dfast=l+k⋅r+r0，其中r是环的周长(2)

由于快指针走过的路程是慢指针的两倍，所以有：

2⋅(l+r0)=l+k⋅r+r0(3)

整理得：

l=k⋅r−r0(4)

即

l=(k−1)⋅r+c(5)

所以，相遇点到入口的距离加上（k-1）个环等于端点到入口的距离。
所以，分别设两个指针从端点和相遇点开始移动，当他们相遇时，即为环的入口。

public class LeetCode142 {
    public ListNode detectCycle(ListNode head) {
        // 利用快慢指针找相遇点
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast)  break;
        }
        if(fast == null || fast.next == null) return null;
        //slow指针从头指针出发，fast指针从相遇点出发
        slow = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}