whoashish's cp notes

Floyd's Cycle Detection

4 min read

Also called the Tortoise and Hare Algorithm.

Purpose: Detect whether a linked list (or functional graph) contains a cycle, and find the starting node of the cycle, in O(n) time and O(1) space.

Algorithm

  1. Use two pointers, slow and fast, both starting at the head.
  2. Move slow one step at a time and fast two steps at a time.
  3. If fast (or fast->next) becomes null, there’s no cycle — stop.
  4. If slow and fast ever meet, a cycle exists.
  5. To find the cycle’s starting node: reset slow to the head, keep fast at the meeting point, and now move both one step at a time.
  6. The point where slow and fast meet again is the start of the cycle.

Code

ListNode* detectCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
 
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            slow = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return nullptr;
}

Paradigm

Decrease and Conquer (two-pointer technique). The gap between slow and fast shrinks by exactly one each step once inside the cycle, progressively reducing the “distance to meeting” until it hits zero — a classic incremental-reduction strategy rather than any split-and-combine or optimization-based approach.

Complexity

  • Time: O(n)
  • Space: O(1)

Proof of Correctness

Part 1 — Why slow and fast must meet if a cycle exists: Once slow enters the cycle, fast is already inside it (since fast moves faster). From that point on, think of the gap between fast and slow measured along the cycle. Each step, fast gains 1 position on slow (moves 2, slow moves 1), so the gap decreases by exactly 1 every step, modulo the cycle length. Since the gap is bounded by the cycle length and strictly shrinks each step, it must eventually hit 0 — meaning they meet. This cannot be skipped over since the gap changes by exactly 1 each time.

Part 2 — Why the second phase finds the cycle start: Let L = distance from head to cycle start, C = cycle length, and let the meeting point be at distance k into the cycle from the start.

When slow and fast meet, slow has traveled L + k steps, and fast has traveled 2(L + k) steps. Since fast completes extra full loops of the cycle:

2(L + k) - (L + k) = L + k = multiple of C  →  L + k ≡ 0 (mod C)  →  L ≡ -k ≡ (C - k) (mod C)

This means the distance from the meeting point to the cycle start (C - k) equals L (mod C) — the same distance from the head to the cycle start. So moving both pointers one step at a time — one from the head, one from the meeting point — makes them arrive at the cycle start simultaneously. ∎

Q) Why do we take 1 and 2 steps?
  • slow moves 1 step and fast moves 2 steps because this gives the simplest and most reliable cycle detection.
  • The relative speed becomes 2 - 1 = 1, so inside a cycle the gap decreases by 1 each time, which guarantees meeting.
  • This also makes the proof clean: when they meet, the second phase can directly find the cycle start.
Q) Why not take other speeds?

In general, you can choose other speeds, but they are not always safe.

  • If slow = 1 and fast = k, then the relative speed is k - 1.
  • They meet only if this relative speed works well with the cycle length.
  • For some cycle lengths, larger speeds can fail to meet.
Example of failure

If the cycle length is 6 and fast = 3, then:

  • slow = 1
  • fast = 3
  • relative speed = 2

Now the gap changes by 2 each time, so it may keep cycling through values like 1, 3, 5, 1... and never become 0.

So the standard choice is:

  • slow = 1
  • fast = 2

because it is always correct and easy to prove.

Variants / Use Cases

  • Find cycle length → once a meeting point is found, keep one pointer fixed and move the other until it returns, counting steps
  • Detect duplicate number in an array (Floyd’s application) → treat array values as a linked list via index-chasing (LeetCode “Find the Duplicate Number”)
  • Happy Number problem → detect cycles in a sequence generated by repeated digit-square-sum
  • Palindrome linked list check → often combined with slow/fast pointers to find the middle before reversing
  • Detecting cycles in functional graphs / iterated functions → general technique beyond linked lists, used in pseudorandom number generator cycle detection (e.g., Pollard’s rho algorithm)

Graph View