Fast-Slow Pointer Technique

The Idea: Two Walkers, Different Speeds

A linked list hides a brutal asymmetry: you can walk forward in $O(1)$ per step, but you cannot index, you cannot look back, and you cannot tell from a node alone whether it sits on a list, on a loop, or near the end. The fast-slow pointer technique — also called the two-pointer trick or Floyd's tortoise and hare — is the most elegant antidote in our toolbox. It says: walk the same list with two pointers at two different speeds, and their relative positions become a measuring device for structure you cannot see directly.

The canonical pair is “slow advances by 1, fast advances by 2.” Concretely, in Python:

1slow = head
2fast = head
3while fast is not None and fast.next is not None:
4    slow = slow.next            # +1 step
5    fast = fast.next.next       # +2 steps

That tiny loop is the basis for at least five separate algorithms. Each one reads off a different invariant of the same simulation:

Application 1 — Find the Middle of a List

Given a singly linked list of $n$ nodes, return the middle node in one pass without computing the length first. The fast-slow recipe makes this almost trivial.

The Invariant

Whenever fast has advanced $2k$ steps from the head, slow has advanced exactly $k$. So when fast falls off the end after $n$ total steps, slow has taken $\lfloor n/2 \rfloor$ steps and is therefore at the middle (rounded down).

Two flavours appear in interview questions, depending on which middle you want for an even-length list:

Application 2 — Detect a Cycle (Floyd's Algorithm)

Robert W. Floyd popularised this algorithm in the late 1960s; it has been rediscovered countless times because the proof is genuinely surprising the first time you see it.

Setup. A list of $n$ nodes either ends in None (no cycle) or loops back to some earlier node (a cycle). Let

• $\mu$ = distance from the head to the cycle entrance (so $\mu = 0$ if the head itself is on the cycle), and
• $\lambda$ = length of the cycle.

Claim. If a cycle exists, slow and fast meet inside it within $\mu + \lambda$ total slow-steps. If no cycle exists, fast hits None in $\lfloor n/2 \rfloor$ slow-steps.

The Catch-Up Argument

Once both pointers are inside the cycle, fast gains exactly one node per step on slow (fast moves 2, slow moves 1, net $+1$). Modulo $\lambda$, the gap between them decreases by 1 each step. A non-negative integer that strictly decreases must hit 0, and once it does, slow == fast: collision detected. So they collide within at most $\lambda$ steps after both are inside.

Both being inside takes at most $\mu$ slow-steps (slow first reaches the entrance after exactly $\mu$ steps; fast is already on the cycle by then because it moves twice as fast). Total work: $O(\mu + \lambda) = O(n)$.

Application 3 — Find the Cycle Entrance

Floyd's real wizardry isn't cycle detection; it's the second phase. Once slow and fast meet, you can locate the exact node where the cycle begins, in $O(n)$ time and $O(1)$ memory, by walking two pointers at speed 1.

The Algorithm

1. Run phase 1 until slow == fast (the meeting point). Call it M.
2. Reset slow to head; leave fast at M.
3. Advance both by exactly 1 step at a time.
4. The first node where they coincide is the cycle entrance. (If the head itself was on the cycle, they coincide immediately at head.)

Why It Works — A Real Proof

Pick the meeting point M. Let $m$ be the distance from the cycle entrance to M measured along the direction of travel (so $0 \le m < \lambda$).

At the moment of collision, slow has taken $\mu + m$ steps. Fast has taken twice as many, $2(\mu + m)$, but fast also went around the cycle some integer number $k \ge 1$ of extra times. So fast's actual path length is $\mu + m + k\lambda$. Setting both expressions for fast's path equal:

$2(\mu + m) = \mu + m + k\lambda \;\Longrightarrow\; \mu + m = k\lambda \;\Longrightarrow\; \mu = k\lambda - m.$

Read this in words: the distance from head to the entrance equals the distance from M to the entrance, modulo $\lambda$. So if you start one walker at head and another at M and step both forward by 1, they will both reach the entrance simultaneously after $\mu$ steps — the head walker by definition, and the M walker because it covers $\mu \equiv -m \pmod{\lambda}$ steps within the cycle, landing at the entrance.

Application 4 — k-th Node from the End

Same machinery, different speeds. To find the $k$-th node from the tail in one pass, use a fixed-gap two-pointer walk:

1. Place lead and trail both at head.
2. Advance lead by exactly $k$ steps. (If it walks off the list, the input has fewer than $k$ nodes — raise.)
3. Now walk both pointers at speed 1 until lead is null. At that moment trail is the $k$-th from the end.

The invariant: lead is always exactly $k$ steps ahead of trail. So when lead reaches null, trail is $k$ nodes behind — which is precisely the definition of “k-th from end.”

This is structurally the same algorithm as middle-finding, with two changes: the gap is $k$ instead of dynamic, and we walk both pointers at speed 1 instead of mismatched speeds. That common skeleton is what makes “two pointers” a single technique rather than five different ones.

Application 5 — Happy Numbers and Functional Iteration

Here is a stunning use of fast-slow that has nothing to do with linked lists. A positive integer is happy if iterating “replace it with the sum of squares of its digits” eventually reaches 1; it is unhappy if the sequence enters a cycle that does not contain 1.

Example for $n = 19$: $19 \to 82 \to 68 \to 100 \to 1$. Happy.

Example for $n = 4$: $4 \to 16 \to 37 \to 58 \to 89 \to 145 \to 42 \to 20 \to 4$. Cycle. Unhappy.

The trick: define $f(x)$ = sum of squared digits of $x$. The sequence $x, f(x), f(f(x)), \ldots$ is a linked list of integers where node.next is $f(\text{node.value})$. Floyd's algorithm tells us whether this list cycles, and the only fixed point is $f(1) = 1$, so “reaches 1” is equivalent to “does not enter a non-1 cycle.”

Interactive: Tortoise & Hare Lab

Pick a topology, set the cycle position with the slider, and step the simulation by hand. Watch slow (green S) and fast (red F) collide inside the loop; then press start phase 2 to launch the head walker (blue H) and see the proof come alive: head and slow each walk one step, and they meet exactly at the cycle entrance.

Try a few experiments to internalise what the variables mean:

• Set $\mu = 0$ (cycle start = 0). Slow and fast meet, and phase 2 immediately reports the entrance as the head — no extra walking needed.
• Make the stem long and the cycle short (e.g. $n = 12$, cycle start = 9). Phase 1 spends most of its time in the stem; phase 2 walks the long way.
• Switch to the straight topology and watch fast outrun slow. When fast hits None, slow is at $\lfloor n/2 \rfloor$ — that is the middle-finding algorithm.

Reference Implementation in Python

These four routines together cover every flavour of fast-slow you will meet in interviews and production code. Read them as variations on the same loop.

Find the Middle

For head = 1→2→3→4→5, slow ends at node 3 (the unique middle).

On a 4-node list 1→2→3→4: iter 1 fast=node3 (fast.next=node4 OK); iter 2 fast=None — loop exits.

After 2 iterations on 1→2→3→4→5→6: slow at node 3 (1+2), fast at node 5 (1+4). After 3 iterations: slow=node 4, fast=None — loop exits.

1def find_middle(head):
2    """Return the middle node. For even n, returns the second of the two middles."""
3    slow = head
4    fast = head
5    while fast is not None and fast.next is not None:
6        slow = slow.next
7        fast = fast.next.next
8    return slow

Detect a Cycle

head=A→B→C→B (C points back to B). Iter 1: slow=B, fast=C. Iter 2: slow=C, fast=C — slow IS fast — return True.

1def has_cycle(head):
2    """Return True if the list contains a cycle, False otherwise."""
3    slow = head
4    fast = head
5    while fast is not None and fast.next is not None:
6        slow = slow.next
7        fast = fast.next.next
8        if slow is fast:
9            return True
10    return False

Find the Cycle Entrance

For head=1→2→3→None: loop exits on fast.next being None; else fires; we return None.

1def cycle_entrance(head):
2    """Return the node where the cycle begins, or None if there is no cycle."""
3    slow = head
4    fast = head
5    while fast is not None and fast.next is not None:
6        slow = slow.next
7        fast = fast.next.next
8        if slow is fast:
9            break
10    else:
11        return None  # while-else: ran to completion without break => no cycle.
12
13    slow = head
14    while slow is not fast:
15        slow = slow.next
16        fast = fast.next
17    return slow

k-th Node from the End

k=2, list 1→2→3→4→5. After sprint: lead=node 3, trail=node 1. Iter 1: lead=4, trail=2. Iter 2: lead=5, trail=3. Iter 3: lead=None — stop. Return node 4 (the 2nd from tail).

1def kth_from_end(head, k):
2    """Return the k-th node from the tail (1-indexed). Raises if k is out of range."""
3    if k < 1:
4        raise ValueError("k must be >= 1")
5
6    lead = head
7    for _ in range(k):
8        if lead is None:
9            raise ValueError("list has fewer than k nodes")
10        lead = lead.next
11
12    trail = head
13    while lead is not None:
14        lead = lead.next
15        trail = trail.next
16    return trail

Same Routines in TypeScript

Here is the same suite ported to TypeScript. The translation is mechanical, but two language-specific details deserve attention: nullability is in the type (we get compile-time help we did not have in Python), and identity vs. equality is unambiguous because === on objects compares references.

1type LNode<T> = { value: T; next: LNode<T> | null };
2
3function findMiddle<T>(head: LNode<T> | null): LNode<T> | null {
4  let slow = head;
5  let fast = head;
6  while (fast !== null && fast.next !== null) {
7    slow = slow!.next;
8    fast = fast.next.next;
9  }
10  return slow;
11}
12
13function hasCycle<T>(head: LNode<T> | null): boolean {
14  let slow = head;
15  let fast = head;
16  while (fast !== null && fast.next !== null) {
17    slow = slow!.next;
18    fast = fast.next.next;
19    if (slow === fast) return true;
20  }
21  return false;
22}
23
24function cycleEntrance<T>(head: LNode<T> | null): LNode<T> | null {
25  let slow = head;
26  let fast = head;
27  let met = false;
28  while (fast !== null && fast.next !== null) {
29    slow = slow!.next;
30    fast = fast.next.next;
31    if (slow === fast) { met = true; break; }
32  }
33  if (!met) return null;
34
35  slow = head;
36  while (slow !== fast) {
37    slow = slow!.next;
38    fast = fast!.next;
39  }
40  return slow;
41}
42
43function kthFromEnd<T>(head: LNode<T> | null, k: number): LNode<T> | null {
44  if (k < 1) throw new RangeError("k must be >= 1");
45  let lead: LNode<T> | null = head;
46  for (let i = 0; i < k; i++) {
47    if (lead === null) throw new RangeError("list has fewer than k nodes");
48    lead = lead.next;
49  }
50  let trail = head;
51  while (lead !== null) {
52    lead = lead.next;
53    trail = trail!.next;
54  }
55  return trail;
56}

Brent's Algorithm — A Faster Cycle Detector

Richard P. Brent (1980) gave a different cycle detection scheme that is asymptotically the same as Floyd's but with smaller constants in practice. The idea: instead of walking both pointers every step, keep slow stationary for $2^k$ fast-steps, then teleport slow to fast and double the budget.

1def has_cycle_brent(head):
2    if head is None or head.next is None:
3        return False
4    slow = head
5    fast = head.next
6    power = 1
7    length = 1
8    while slow is not fast:
9        if fast is None or fast.next is None:
10            return False
11        if length == power:
12            slow = fast
13            power *= 2
14            length = 0
15        fast = fast.next
16        length += 1
17    return True

Why is this faster in practice? Floyd does two pointer dereferences per step (slow + fast); Brent does one (only fast moves). When pointer chasing is the bottleneck (almost always, on real hardware where each node.next is a cache miss), halving the dereferences halves the wall-clock time. Brent also discovers $\lambda$, the cycle length, as a free side effect — useful for Pollard's rho.

Where Fast-Slow Pointers Run in Production

Operating Systems and Memory

• Garbage collectors use cycle detection variants when freeing reference-counted objects: a cycle of references would otherwise leak forever. CPython's gc module is the canonical example, though it uses a different (graph-based) algorithm; embedded reference-counting allocators in C++ smart-pointer libraries use Floyd-style detection on suspicious sub-graphs.
• Memory leak detectors in Linux kernel modules walk allocator linked lists and apply Floyd to detect circular corruption from buggy drivers.
• Filesystem fsck tools use cycle detection when verifying that the directory tree is actually a tree (no cycles via misplaced hard links on systems where directory hard-linking is permitted).

Compilers and Language Runtimes

• Module loaders (Python's import system, Node's require, Java's class loaders) detect circular imports during dependency resolution. The classical approach uses an explicit visited set, but in low-memory bootloaders the fast-slow trick gets used on the “currently resolving” stack.
• Type-inference engines for languages with structural types must detect cycles in type-alias chains: type A = B; type B = C; type C = A; — a cycle Floyd's detects in $O(1)$ memory.

Networking and Distributed Systems

• Routing protocols use TTL fields as a poor-man's cycle bound, but on the control plane, link-state databases run cycle detection over forwarding tables to catch routing loops.
• Distributed-deadlock detection: the wait-for graph among lock holders forms a directed structure where a cycle = deadlock. Banker's and Chandy-Misra-Haas algorithms use cycle-detection primitives related to fast-slow.

Cryptography and Number Theory

• Pollard's rho factorization — the most famous application. To factor an integer $N$, iterate $f(x) = x^2 + 1 \bmod N$ and run Floyd's on the sequence. When you find a collision, $\gcd(|x - y|, N)$ often gives a non-trivial factor. Expected time $O(N^{1/4})$ by the birthday paradox.
• Pollard's rho for discrete logarithms uses the same skeleton in cryptanalysis of weak elliptic-curve parameters.
• Pseudorandom-number-generator validation: any deterministic PRNG over a finite state space must eventually cycle; Floyd or Brent detects the period. Engineers running statistical simulations check this to ensure their generator's period exceeds the simulation length.

Algorithms Interviews and Competitive Programming

• Find the Duplicate Number (Leetcode 287). Given an array of n+1 integers in [1, n] with one duplicate, use values as pointers (i → nums[i]); the duplicate is the entrance of a cycle. $O(n)$ time, $O(1)$ memory — a result that astonished interviewers when first popularised.
• Linked List Reorder, Palindrome Check, Rotate by k — all rely on middle-finding via fast-slow as a subroutine.
• Intersection of Two Linked Lists uses a related two-pointer trick: walk both, switch heads when one runs out, and you are guaranteed to meet at the intersection (or both at None) after at most $m + n$ steps.

Robotics, AI, and Everyday Software

• State-machine cycle detection in autonomous-driving planners: a planner exploring possible state sequences must avoid revisiting equivalent states; Floyd's runs on the canonical-state hash chain.
• Spreadsheet circular-reference detection: every time you type =A1 into cell A1, Excel runs a cycle check on the dependency graph — a problem with elegant fast-slow flavour when the graph is sparse.
• Database query planners: view-resolution traversal must detect circular view definitions (view A references view B references view A), often via Floyd-style detection during the planner's dependency walk.

Pitfalls and How to Avoid Them

1. NullPointer on fast.next.next. Always guard with both fast is not None AND fast.next is not None. Dropping the second check kills the program on any odd-length list at the last iteration.
2. Off-by-one in middle-finding. while fast and fast.next vs. while fast.next and fast.next.next give different middles for even $n$. Pick one and document it.
3. Using == instead of is (or === in TS). Identity, not equality, is what cycle detection requires. Two distinct nodes can carry equal values.
4. Phase 2 with speed 2. The cycle-entrance proof requires both pointers walking by 1 in phase 2. Speed 2 lands on the wrong node.
5. Resetting the wrong pointer. In phase 2, reset slow to head; do not reset fast. Fast must stay at the meeting point M for the math to work.
6. Forgetting $\mu = 0$ case. If the head itself is on the cycle, phase 2 must return head immediately. Both reference implementations above handle this because the while slow is not fast guard checks before stepping.
7. k-th-from-end with k = list length. The sprint loop walks lead off the tail and into None exactly when k equals the length; the lockstep loop then runs zero times and returns head — correct. Test this boundary explicitly.
8. Mutating during traversal. If you delete or splice nodes while a cycle-detection pass is in flight, all bets are off. Either snapshot a list of (prev, curr) pairs and operate on it afterwards, or hold a lock.

Quick Checks

Fast-slow pointers are the kind of trick you only need to understand once. Internalise the catch-up argument and the $\mu = k\lambda - m$ identity, and a whole family of problems — middle, cycle, entrance, k-from-end, happy numbers, Pollard's rho — collapses into one short loop. In the next section we will look at “When to Use Linked Lists vs Arrays” and revisit why the techniques that make linked lists tolerable do not change the underlying cache-locality verdict.