Proofs

Definitions

• $A$: Beginning of the linked-list
• $B$: Intersection point of the circle
• $M$: Meeting point of fast / slow pointers
• $x$: Distance from $A$ to $B$
• $y$: Distance from $B$ to $M$
• $C$: Perimeter of the cycle

Procedure

We already know the fast pointer has twice the speed as the slow pointer, the fast pointer can go through multiple cycles before it meets the slow pointer. Based on this, we have the following equation:

$$ \begin{align} x + kC + y &= 2(x + y) \\[1em] kC &= x + y \\[1em] kC - y &= x \end{align} $$

Now, put two pointers with the same speed to $A$ and $M$, consider when both of them go through a distance of $x$.

• The pointer previously starting at $A$ will now go to $B$.
• The pointer previously starting at $M$ will now go to $B$, too.

To proof the second point, consider the offset between $B$ and the pointer started at $M$. The initial offset is $y$, and after going through $x$, we got:

$$ \begin{align} \text{offset}' &= y + x \\[1em] &= y + kC - y \\[1em] &=kC \end{align} $$

This proves the pointer starting at $M$ must be at the point $B$ at this point.

Now we know, the pointer will meet each other at point $B$ after going through a distance of $x$. And before reaching point $B$, the pointer starting at $A$ will never be able to meet with another pointer, so it is easy to prove this meet will be the first meet of these two pointers.

Code Example

LeetCode Question

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* move(ListNode* pointer, unsigned int step = 1) {
        while (pointer != nullptr && step--) {
            pointer = pointer->next;
        }
        return pointer;
    }

    ListNode* detectCycle(ListNode* head) {
        // be f**king careful about this...
        // if ignore these two lines, the while loop below 
        // will not get a chance to start at all!
        ListNode* fast = head;
        ListNode* slow = head;

        while (fast != slow && fast != nullptr) {
            fast = move(fast, 2);
            slow = move(slow, 1);
        }

        if (fast == nullptr) {
            return fast;
        }

        slow = head;
        while (fast != slow) {
            fast = move(fast, 1);
            slow = move(slow, 1);
        }

        return fast;
    }
};