Linked List Cycle II

Problem Statement

Given the head of a linked list, return the node where a cycle begins. If there is no cycle, return null.

You must solve it using O(1) memory.

Input:  3 → 2 → 0 → -4
             ↑        ↓
             ←————————
Output: the node with value 2  (index 1)

Input:  1 → 2 → 1 (cycle back to the head)
Output: the node with value 1

Input:  1 → null
Output: null

Intuition

There are two questions here: is there a cycle? and where does it start? The first is easy; the second is where the famous trick lives.

Part 1 — detecting the cycle

That "gain exactly one per step" argument is why fast moves by two and not three. With a larger stride the gap changes by more than one and could step over slow on a loop whose length shares a factor with the stride.

Part 2 — locating the cycle's start

This is the surprising part. Label the distances:

head ──── F ────► S ──── a ────► M
                  ▲               │
                  └───── b ───────┘

F = distance from head to the cycle start S
a = distance from S forward to the meeting point M
b = remaining distance from M back around to S
C = a + b = cycle length

When they meet:

• slow has travelled F + a (it enters the loop and walks a).
• fast has travelled F + a + nC for some whole number of extra laps n ≥ 1.
• fast moved twice as far: 2(F + a) = F + a + nC.

Simplify: F + a = nC, so F = nC - a = (n-1)C + (C - a) = (n-1)C + b.

Watch it run

Approach

Solution

from typing import Optional


class ListNode:
    def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
        self.val = val
        self.next = next


def detect_cycle(head: Optional[ListNode]) -> Optional[ListNode]:
    """Return the node where the cycle begins, or None."""
    slow = fast = head

    # Phase 1: find a meeting point inside the cycle.
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None  # fast ran off the end — no cycle

    # Phase 2: F == b, so both pointers reach the entrance together.
    finder = head
    while finder is not slow:
        finder = finder.next
        slow = slow.next

    return finder

The hash-set version

If O(n) memory is acceptable, the problem becomes almost trivial:

def detect_cycle_set(head: Optional[ListNode]) -> Optional[ListNode]:
    seen = set()
    node = head

    while node:
        if id(node) in seen:
            return node  # first revisited node IS the cycle start
        seen.add(id(node))
        node = node.next

    return None

Worth mentioning in an interview as the obvious baseline before presenting Floyd's — it shows you know the trade-off rather than just the trick.

Complexity Analysis

• Time — phase 1 takes at most O(n) steps (slow cannot travel further than the list length plus one lap); phase 2 takes F ≤ n steps.
• Space — four references. This is the whole reason to prefer Floyd's over the hash set, which needs O(n).

Edge Cases

Related Problems

• Middle of the Linked List — the gentle introduction to fast and slow pointers
• Intersection of Two Linked Lists — pointers synchronised by a distance argument
• Reverse Linked List — careful pointer handling