Linked List Cycle II

Hints

1. The hash-set baseline. Walk the list, insert each node into a set, return the first node already seen. O(n) time, O(n) memory. This works but doesn't satisfy the "O(1) memory" constraint.
2. Detect the cycle first. Two pointers: slow advances by one, fast by two. If a cycle exists, fast eventually catches up to slow inside it. If not, fast reaches null.
3. Why fast and slow meet. Once both are inside the cycle of length L, fast gains exactly one position per iteration. After at most L iterations, the gap closes to zero. That's the meeting moment.
4. Locating the entry: the math. Let μ be the distance from head to cycle start, L the cycle length. The meeting happens at some position k inside the cycle. Algebra (see the deep-dive) gives μ ≡ L − k (mod L).
5. The geometric consequence. Walk one pointer from the head and another from the meeting point, both at speed 1. They will coincide at the cycle's entry: exactly μ steps from the head, and (L − k + μ) ≡ 0 (mod L) steps from the meeting point.
6. Implementation rhythm. Phase 1: detect with fast/slow until they meet (or fast hits null). Phase 2: reset slow to head, advance both at speed 1 until they meet. Return the meeting node.

Solution: three approaches

Approach 1 · Hash set: O(n) time, O(n) space

The simplest correct answer. Insert each node into a set as you walk; return the first node that's already in the set.

def detect_cycle_hash(head):
    seen = set()
    curr = head
    while curr is not None:
        if curr in seen:
            return curr
        seen.add(curr)
        curr = curr.next
    return None

Easy to write, easy to verify. But the O(n) memory cost violates the problem's constraint, and on large lists the cache footprint of the hash set hurts wall-clock time. This is the warm-up answer.

Approach 2 · Floyd's algorithm: O(n) time, O(1) space

The canonical answer. Two phases: detect, then locate.

def detect_cycle(head):
    # Phase 1: detect via fast/slow.
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None                  # no cycle (Python while-else)

    # Phase 2: locate the entry. Reset slow to head; advance both at speed 1.
    slow = head
    while slow is not fast:
        slow = slow.next
        fast = fast.next
    return slow

Why phase 1 works: if the list has no cycle, fast reaches null. If it does, both pointers eventually enter the cycle; once inside, fast gains one node on slow per iteration. The cycle has finite length, so they coincide.

Why phase 2 works: let μ be the distance from head to cycle start, L the cycle length, and k the position of the meeting point measured forward from the cycle's entry. At the meeting moment, slow has walked μ + k steps; fast has walked 2(μ + k) steps. Fast also walked μ + m·L + k for some integer m ≥ 1. Equating: 2(μ + k) = μ + m·L + k, which simplifies to μ = m·L − k, or equivalently μ ≡ L − k (mod L).

Now restart slow at head and advance both pointers one step at a time:

• The pointer from head has walked exactly μ steps when it reaches the cycle's entry.
• The pointer from the meeting point has walked the same number of steps. Since μ ≡ L − k (mod L), it has rotated through the cycle by exactly L − k positions, landing at position 0, the cycle's entry.

So they meet at the entry. The proof is exact, not approximate.

Approach 3 · Brent's algorithm: O(n) time, O(1) space

An alternative cycle-detection algorithm that uses fewer pointer dereferences than Floyd's. Less commonly asked in interviews; included for completeness.

# Brent's: power-of-two doubling of slow, with fast advancing one at a time.
def detect_cycle_brent(head):
    if head is None: return None
    power = lam = 1
    tortoise = head
    hare = head.next
    while hare is not None and hare is not tortoise:
        if power == lam:
            tortoise = hare
            power *= 2
            lam = 0
        hare = hare.next
        lam += 1
    if hare is None:
        return None
    # Find the entry: advance one pointer by lam, then walk together.
    tortoise = hare = head
    for _ in range(lam):
        hare = hare.next
    while tortoise is not hare:
        tortoise = tortoise.next
        hare = hare.next
    return tortoise

Same asymptotic complexity, slightly fewer pointer follows in practice. Floyd's is the one to learn first; Brent's is a footnote.

Complexity comparison

Edge cases to verify

• Empty list: head = None → None. The phase-1 loop's guard fast is not None fires immediately.
• Single node, no cycle: 1 → null → None. fast = head; fast.next is None; loop terminates without a meeting.
• Single node, self-loop: 1 → 1 → node 1. Phase 1 meets immediately on the first iteration; phase 2 with slow at head and fast at node 1 (they're equal) returns node 1.
• Cycle starts at head: e.g. 1 → 2 → 3 → 1. μ = 0; phase 2 returns immediately because slow == fast == head before the while loop body runs.
• No cycle: 1 → 2 → 3 → null. Phase 1's while-else triggers; return None without entering phase 2.

Where beginners go wrong

• Skipping the null guard on fast.next. Without checking both fast is not None AND fast.next is not None before fast = fast.next.next, the no-cycle case crashes. Both checks are required.
• Restarting fast instead of slow in phase 2. The identity μ ≡ L − k (mod L) requires walking from head while fast stays at the meeting point. Reversing them produces wrong answers (sometimes by accident the right one, but not in general).
• Comparing values with == instead of identity with is. Two distinct nodes can have equal values; the algorithm needs reference equality. slow is fast, not slow.val == fast.val.
• Trying to count cycle length first. Some students compute L (cycle length) by continuing fast inside the cycle until it returns to slow, then walk fast L steps from head and march both pointers forward. This works, but it costs two extra passes; Floyd's two-phase approach gets the same answer in fewer steps.
• Forgetting that no-cycle is a valid input. Phase 2 must only run when phase 1 actually met. The Python while-else idiom handles this; in other languages, a boolean flag does the job.

Interview follow-ups to expect

• "Find the cycle's length." After phase 1 meets, hold one pointer fixed and let the other walk until it returns. Count the steps. O(L), O(1).
• "Remove the cycle." Find the entry with phase 2. Then walk to the node whose next is the entry, set its next to null. Cycle removed.
• "Apply Floyd's to an array: Find the Duplicate Number." Treat i → nums[i] as the implicit "next" function. The duplicate value forces a cycle whose entry is the duplicate itself. See the Floyd deep-dive.
• "Detect a cycle in a graph rather than a list." DFS with a "currently in the recursion stack" set. Floyd's is specific to functional graphs (where each node has exactly one outgoing edge); general graphs need a different approach.
• "What if the list is doubly linked?" Same algorithm, since Floyd's only uses next; the prev pointers don't change anything. The doubly-linked structure does enable a different algorithm (start from head, walk forward while marking visited via prev manipulation), but Floyd's is still simpler.

Related reading

• Floyd's Tortoise & Hare: the deep-dive that proves the modular-arithmetic identity in full and applies the technique to implicit graphs.
• In-Place Reversal Patterns, the other classic linked-list pointer drill.
• Linked Lists, the module that frames why pointer discipline matters.