Question

link

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?

Stats

Adjusted Difficulty 5
Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is an famous question, historically know as the Tortoise and hare.

Solution

This blog has a great solution.

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

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

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

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

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

=>   X+K  =  (m-2n)Y    ③

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

Code

public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null)
        return null;
    ListNode first = head.next, second = first.next;
    ListNode found = null;
    while (first != null && second != null) {
        if (first == second) {
            found = first;
            break;
        }
        first = first.next;
        second = second.next;
        if (second == null) break;
        second = second.next;
    }
    if (found == null) return null;
    first = head;
    while (first != second) {
        first = first.next;
        second = second.next;
    }
    return first;
}