Fast & Slow Pointers

Application 1. Cycle detection

The original use. If a linked list has a cycle, slow and fast both eventually enter it; once inside, fast catches up. If no cycle, fast reaches null.

def has_cycle(head):
    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:
            return True
    return False

O(n) time, O(1) memory. The hash-set alternative is also O(n) but uses O(n) memory; on memory-constrained systems, fast/slow wins decisively. The full proof of why this works (and why a clever restart locates the cycle's entry) is in the Floyd's deep-dive.

Application 2. Midpoint

When fast reaches the end, slow has walked exactly half the distance. So slow ends at the midpoint.

def middle_node(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

For even-length lists, this returns the second middle (because fast falls off at fast.next is None when slow is at index n/2). For odd-length lists, slow is exactly at the centre. Both behaviours are usually what callers want; if you specifically need the first middle on even lists, use while fast.next is not None and fast.next.next is not None.

The midpoint trick is the foundation of "palindrome linked list", reverse the second half, then compare with the first half, all in O(n) time and O(1) memory.

Application 3. Palindrome linked list

def is_palindrome(head):
    # 1. Find the midpoint.
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

    # 2. Reverse the second half (starting at slow).
    prev = None
    while slow is not None:
        nxt = slow.next
        slow.next = prev
        prev = slow
        slow = nxt

    # 3. Compare the two halves.
    left, right = head, prev
    while right is not None:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    return True

O(n) time, O(1) memory. The naïve approach copies the list to an array and uses two pointers from the ends, also O(n) but O(n) memory. Fast/slow + reverse is the version that earns the question.

Application 4. Find the duplicate number

"Array of n+1 integers, each in [1, n]. By pigeonhole, at least one value appears twice. Find it in O(n) time, O(1) memory, without modifying the array."

Treat i → nums[i] as the "next" function of an implicit graph. The duplicate value forces a cycle in that graph; its entry is the duplicate. Floyd's algorithm applied to this graph finds it.

def find_duplicate(nums):
    slow = fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow

The constraint forbids modifying the array, which rules out sorting and rules out marking-by-negation. Fast/slow is the only standard technique that satisfies all three constraints (O(n), O(1), no mutation).

Variants worth knowing

Triple pointers, find the K-th node from the end

Advance fast by K steps first; then advance both slow and fast together. When fast reaches the end, slow is K steps behind.

def kth_from_end(head, k):
    slow = fast = head
    for _ in range(k):
        if fast is None: return None
        fast = fast.next
    while fast is not None:
        slow = slow.next
        fast = fast.next
    return slow

Reorder linked list, interleave halves

Find midpoint, reverse second half, interleave. All three subroutines use fast/slow or its descendants. The final list is L₀ → Lₙ → L₁ → Lₙ₋₁ → L₂ → Lₙ₋₂ ...

Happy number

Repeatedly sum squares of digits until you reach 1 or cycle. The "or cycle" detection uses fast/slow on the implicit functional graph defined by the digit-square-sum function.

When to reach for it

• Linked list problems involving cycles, midpoints, or "K steps before the end".
• Array problems with an implicit "next" function, i → a[i], x → digit_sum(x), anything where each element maps to one other.
• O(1) memory constraint, hash-set alternatives are easier to code but use O(n) memory.
• Streaming / immutable input, when you can't modify the data or store much.

Where beginners go wrong

• Null-deref on fast. Before fast = fast.next.next, both fast and fast.next must be non-null. Check both.
• Confusing midpoint conventions. Even-length lists have two midpoints; pick the one your problem wants and write the loop condition accordingly.
• Trying it on graphs that aren't functional. Fast/slow requires that each node has exactly one outgoing edge. General graphs need DFS or BFS, not this technique.
• Modifying the array when you shouldn't. The "find the duplicate" problem explicitly forbids modification; using marking-by-negation (a common O(n) O(1) technique) violates the constraint.
• Using == when you want object identity. In linked-list code, slow is fast compares references, the intended semantics. slow == fast may compare values and produce false positives.

What to read next

The Floyd's Tortoise & Hare deep-dive proves the modular-arithmetic identity that locates cycle entries. The Converging Pointers piece covers the cousin pattern where pointers move toward each other. The Two Pointers module ties all the variants together.