p08 Linked List Cycle — Progressive Hints

Rule: Read ONE hint. Set a 5-minute timer. Try again. Only read the next hint if the timer expires.

Hint 1 — Pattern family

You can solve this with extra memory (remember every node you’ve seen — if you revisit one, cycle). Can you do it WITHOUT extra memory? Think about two things moving through the list at different speeds.

Hint 2 — Data structure / state

Two pointers. Both start at head. One advances by 1 each iteration; the other by 2. If there’s a cycle, the faster one will eventually lap the slower one and they’ll be at the same node. If no cycle, the faster one walks off the end.

Hint 3 — The key insight

Inside any cycle of length C, the gap between fast and slow (fast minus slow, mod C) increases by exactly 1 each step. Since the gap is bounded in [0, C-1], it must take the value 0 within C steps — that’s when they meet. The algorithm is guaranteed to terminate, with proof.

For the no-cycle case: fast (moving 2 per step) reaches the end (None) in at most N/2 steps.

Hint 4 — Pseudocode skeleton

slow = head
fast = head
while fast is not None and fast.next is not None:
    slow = slow.next
    fast = fast.next.next
    if slow is fast:
        return True
return False

Two correctness checks: (a) you guard BOTH fast AND fast.next before doing fast.next.next, (b) you advance then compare (not compare before the first advance, which would falsely return True for any list of length ≥ 1).

Hint 5 — Full algorithm + why this works

Floyd’s tortoise-and-hare: start slow = fast = head. In each loop iteration: advance slow by 1, fast by 2. If fast or fast.next is None, no cycle exists. If slow and fast point to the same node, a cycle exists.

Why speeds (1, 2) specifically: the gap between them increases by 2 - 1 = 1 per step (mod cycle length C). Since gcd(1, C) = 1 for any C, the gap eventually equals 0 — they meet. If you used (1, 3), the gap would increase by 2 per step; for even C, the gap might be permanently odd and never hit 0. The choice isn’t arbitrary; it guarantees correctness for all cycle lengths.

Why fast and fast.next BEFORE advancing fast by 2: because fast.next.next would crash on NoneType otherwise. The guard goes BEFORE the advancement.

HashSet variant (correctness oracle): walk the list, store id(node) in a set; if you encounter a duplicate id, return True. Use id() (identity), not node.val, because two distinct nodes can hold the same value — [1, 1, 1, 1] with no cycle would falsely trigger on val.

Time O(N) both; space: HashSet O(N), Floyd’s O(1). Floyd’s wins in interviews and production.