Fast & Slow Pointers

TL;DR

Walk a sequence with two pointers where one moves twice as fast as the other. On a finite structure with a cycle, the fast pointer eventually laps the slow one and they collide; on a structure without a cycle, the fast pointer falls off the end first. That single observation — Floyd’s tortoise and hare — solves three otherwise-annoying linked-list problems in O(1) extra space.

The three flavors you’ll actually use:

• Cycle detection (LC 141) — does this linked list (or functional iteration) loop?
• Cycle start (LC 142) — which node is the entry point of the loop?
• Middle of list (LC 876) — find the midpoint in one pass, no length precompute.

The same skeleton also cracks LC 287 (Find the Duplicate Number) and LC 202 (Happy Number) by treating nums[i] or digit_square_sum(n) as a pointer function. If your problem can be modeled as “follow next from a starting state until you repeat,” fast-slow is almost always the right tool.

The picture in your head

Tortoise and hare on a circular track. The tortoise plods one step per tick; the hare bounds two. If the track is a straight line that ends at a cliff, the hare falls off first and the race is over — no cycle. If the track loops back on itself, both animals eventually find themselves running laps inside the loop, and the hare is gaining exactly one step per tick on the tortoise. Inside any finite ring, “gaining one step per tick” guarantees the hare catches the tortoise within C ticks, where C is the loop length.

That’s flavor 1. The slightly magical part is flavor 2: the spot where they collide is mathematically tied to where the loop begins. Walk the same distance from the start of the track and from the collision point at equal speed, and the two walkers meet exactly at the loop’s entry. The math falls out of “the hare walked twice as far as the tortoise” — no more, no less.

The problem it solves

Given a linked list, decide if it cycles. Brute force: keep a hash set of nodes you’ve already visited, walk forward, return True the moment you see a familiar node.

def has_cycle_brute(head: ListNode | None) -> bool:
    seen: set[int] = set()
    node = head
    while node is not None:
        if id(node) in seen:
            return True
        seen.add(id(node))
        node = node.next
    return False

That’s O(n) time and O(n) space. Correct, easy to write, and wasteful. The space cost is the part that bites:

• Embedded / kernel code. A linked-list scanner inside an OS scheduler or a microcontroller firmware can’t malloc a hash set the size of the list it is checking — there may not be a heap to allocate from.
• Multi-million-node lists. Streaming log indexes, intrusive lists in databases, and on-disk skip lists routinely hold tens of millions of nodes. An auxiliary hash set the same size doubles peak RSS during a cycle scan.
• Cache pressure. Even when you can afford the memory, the hash-set probes evict everything else from L2 — cycle scans you do “in passing” during normal traversal want zero side effects on cache.

Floyd’s two-pointer trick keeps the O(n) time and drops the space to O(1): two pointer variables, period. That’s the entire reason this pattern is worth memorising.

When to reach for it

Signals it’s the right move:

• The structure is a linked list (or any “follow a successor function” iteration) and the question is about cycles, midpoint, or k-from-end.
• You need O(1) extra space. The hash-set baseline above works but costs O(n) memory; fast-slow is the constant-space answer interviewers and production systems want.
• The problem can be reframed as x → f(x) → f(f(x)) → .... Find-the-Duplicate on nums works because i → nums[i] defines a functional graph with exactly one cycle.

Signals it’s not fast-slow: you need the cycle’s length without the math (use a hash set + counter), the structure is a tree or DAG (use DFS with visited / colors), or the iteration function isn’t deterministic.

Flavor 1 — cycle detection (LC 141)

def has_cycle(head: ListNode | None) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Worked example. Six nodes (indices 0..5), with the tail wired back to node 3 — so the cycle is 3 → 4 → 5 → 3:

0 → 1 → 2 → 3 → 4 → 5
            ↑_______|

Both pointers start at node 0. Each step: slow advances 1, fast advances 2. Indices inside the cycle wrap (after 5 comes 3).

They collide at node 3 — which happens to also be the cycle start in this particular example. Why this must happen: once slow enters the cycle, both pointers are looping inside a finite ring. On every step, fast gains one position on slow (it moves 2, slow moves 1, net gap +1). The gap is bounded by the cycle length C, so within at most C steps the gap wraps back to 0 and they meet. If the list has no cycle, fast or fast.next hits None first and the loop exits.

Flavor 2 — find the cycle start (LC 142)

Once you know there’s a cycle, finding where it starts is the part that looks like magic until you do the algebra.

def cycle_start(head: ListNode | None) -> ListNode | None:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None
    if not fast or not fast.next:
        return None

    # phase 2: one pointer from head, one from meeting point, both step by 1
    p = head
    while p is not slow:
        p = p.next
        slow = slow.next
    return p

The math. Let L = distance from head to cycle start, C = cycle length, k = distance from cycle start to the meeting point (measured forward inside the cycle). When they meet:

• slow has walked L + k steps.
• fast has walked 2(L + k) steps and is at the same node, so its extra distance is a whole number of laps: 2(L + k) − (L + k) = L + k = nC for some integer n ≥ 1.
• Therefore L = nC − k. In words: walking L steps from the meeting point forward lands you exactly at the cycle start (you complete n − 1 full laps and then the last C − k steps to the entry).

So: reset one pointer to the head, leave the other at the meeting point, advance both by 1. They converge at the cycle start.

Worked example with different geometry. Take a 7-node list 0..6 with the tail (6.next) wired back to node 2. So L = 2, cycle is 2 → 3 → 4 → 5 → 6 → 2, C = 5.

Phase 1 trace:

Meet at node 5. So k = 3 (steps from cycle start 2 forward to 5: 2 → 3 → 4 → 5). Check the algebra: L + k = 2 + 3 = 5 = 1 · C. Consistent.

Phase 2, p from head, slow stays at the meeting node, both step by 1:

Converge at node 2 — the cycle start. Done.

Flavor 3 — middle of a linked list (LC 876)

def middle(head: ListNode | None) -> ListNode | None:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

When fast falls off the end, slow is sitting on the middle. For odd length it’s the exact middle; for even length it’s the second middle (swap the loop condition to fast.next and fast.next.next if you want the first).

Trace on 1 → 2 → 3 → 4 → 5:

fast.next is None, loop exits, return slow = 3. One pass, no length precomputation, no second traversal.

Why it works — the invariant

Every iteration, fast moves 2 and slow moves 1, so fast gains exactly 1 position on slow per step. That single fact carries all three flavors:

• Cycle detection. Once both are inside the cycle, the relative gap shrinks (or grows, depending on how you count) by 1 mod C each step. After at most C steps the gap is 0 and they collide. No cycle ⇒ fast runs out of nodes first.
• Cycle start. fast traverses double the distance of slow in the same number of steps, which forces L + k ≡ 0 (mod C), which is exactly the equation that makes the head-and-meeting-point walk converge.
• Middle. fast reaches the end in n/2 steps; in those same steps slow walks n/2 nodes, putting it on the midpoint.

If you can’t articulate the “+1 per step” invariant for your problem, the pattern probably doesn’t apply — reach for a hash set instead.

Complexity & memory tradeoffs

Time is the same across all three — you have to look at every node at least once. Space is where Floyd’s wins: two stack-allocated pointers versus an n-entry hash set is the difference between a function that runs inside an interrupt handler and one that can’t.

The phase-2 cost in flavor 2 is L more steps (head to cycle start), so total work is bounded by L + C + L ≤ 2n — still linear. Middle-of-list is exactly n/2 slow steps. All three flavors are O(n) time, O(1) space.

The only time the hash-set baseline wins is when you also need a side output the pointer trick can’t give you cheaply — e.g. the full list of visited nodes, or a count of how many distinct nodes preceded the cycle. If all you need is “is there a cycle / where does it start / what’s the midpoint,” fast-slow strictly dominates.

Common pitfalls

• Missing None checks on fast.next.next. The loop guard must be while fast and fast.next — if you only check fast, you crash on fast.next.next at the end of an acyclic list.
• Off-by-one when initialising. Starting fast = head.next instead of fast = head is a valid variant but it shifts every meeting point by 1 and breaks the L = nC − k algebra used in flavor 2. Pick one convention (both at head) and keep it everywhere.
• Forgetting phase 2 needs the meeting point, not the head. A common bug is to reset both pointers to head after the meet, which obviously finds nothing. Only one resets; the other stays at the meeting node.
• Returning the wrong middle on even length. 1 → 2 → 3 → 4 returns 3 with the canonical loop, not 2. If your problem (e.g. splitting a list for merge sort) needs the first middle, change the guard.
• Applying it to non-iterable structures. Fast-slow requires a single successor function. On trees, graphs with branching, or any structure where “next” isn’t unique, the +1-per-step invariant evaporates and the pattern silently gives wrong answers.

Where you see this in production

Floyd’s algorithm shows up well outside linked-list interview questions:

• CPython gc module — cyclic garbage collection. Reference counting can’t free objects that point at each other in a cycle (e.g. a.x = b; b.x = a). The gc module’s job is to find those cycles. Production CPython uses generational mark-and-sweep, but the underlying problem — “follow __refs__ from a root and decide if you loop” — is the same one Floyd solves, and the algorithm shows up directly in cycle-validation helpers in the CPython test suite.
• Bazel / Buck2 dependency cycle detection. During target resolution a build graph walker follows deps edges. A Floyd-style two-speed walk is a cheap pre-check before the full Tarjan SCC pass that produces the human-readable “//foo:bar depends on //baz:qux depends on //foo:bar” error. The same trick lives in npm/pnpm peer-dependency resolution and in Cargo’s dependency solver.
• Blockchain ledger validation. A blockchain is a singly linked list of blocks via prev_hash. A malicious or corrupted node can produce a forked chain whose prev_hash pointers cycle back on themselves; light clients use a Floyd-style scan during header sync to reject such chains in O(1) memory rather than buffering every header into a hash set.
• Doubly linked list internals — Linux kernel list.h. Self-checking builds of the kernel (CONFIG_DEBUG_LIST) validate that intrusive doubly linked lists are well-formed before each mutation. Walking with a fast-slow pair detects corruption-induced cycles without allocating — critical inside contexts like interrupt handlers where allocation is banned outright.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.