AlgoScope

Fast and Slow Pointers

algorithmintermediateTime O(n)Space O(1)

A list has no index, so you cannot jump to the middle or the end. Two pointers moving at different speeds get you there anyway, in one pass and with no counting.

1234567fastheadslow

Find the middle of a list with no index. Two pointers start at the head; slow moves one node per step, fast moves two. When fast runs out, slow is halfway.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.

  1. Fast is about to jump two. Does it reach a node, or run out?

    • Reaches a node
    • Runs out

    Answer: Reaches a node. Two nodes ahead still exists, so fast lands there.

  2. Fast is about to jump two. Does it reach a node, or run out?

    • Reaches a node
    • Runs out

    Answer: Reaches a node. Two nodes ahead still exists, so fast lands there.

  3. Fast is about to jump two. Does it reach a node, or run out?

    • Reaches a node
    • Runs out

    Answer: Reaches a node. Two nodes ahead still exists, so fast lands there.

How it runs, step by step

  1. Find the middle of a list with no index. Two pointers start at the head; slow moves one node per step, fast moves two. When fast runs out, slow is halfway.

    Finding the middle node with a slow pointer and a fast pointer.

  2. Step 1: slow moves to 2, fast jumps two to 3.

    Slow is at 2. Fast is at 3.

  3. Step 2: slow moves to 3, fast jumps two to 5.

    Slow is at 3. Fast is at 5.

  4. Step 3: slow moves to 4, fast jumps two to 7. Fast has nowhere left to go.

    Slow is at 4. Fast is at 7.

  5. Fast is done after 3 steps, and slow sits on 4, index 3 of 7. Half the walk, one pass, no counting first.

    The middle node is 4.

Write it yourself

Define middleIndex(values) and return the position of the middle node, counting from 0, taking the second of two. It runs in your browser against this lesson's own 2 examples.

// Move one pointer one step and the other two. When the fast one runs out, the slow one is in the middle.function middleIndex(values) {    return 0;}
Ln 1, Col 16 linesTab indents; Escape then Tab leaves the editor. Ctrl-Enter runs, Cmd-Enter on a Mac.

Remember

  • When fast runs out, slow is at the middle. When fast lands on slow, the list loops.
  • After the pointers meet in a loop, restart one at the head and walk both by one to find the entry.
  • A fixed gap between two pointers finds the nth from the end without knowing the length.

Topics covered

Related

Where this is used

CryptographyPollard's rho factorisation

Pollard's rho factors an integer by iterating x -> x * x + c mod n until the sequence repeats, because the repeat is what exposes a factor through a gcd. Nothing is stored: the walk is expected to run for about the fourth root of n steps before it comes back on itself, already ten billion values for a 40-digit n, so the repeat has to be caught with a few registers rather than a table. Pollard used the two-speed walk for that. GNU coreutils' factor ships the same algorithm with Brent's variant of the cycle search, which holds one saved value and compares against it over runs of doubling length instead of stepping a second cursor.

Systems librariesSplitting a list in GLib's sort

g_list_sort walks a GList with two cursors, advancing one by a single node for every two the other takes, then cuts the list where the slow cursor stopped and merge sorts the two halves. A GList carries no length field, so counting the nodes first would mean an extra full traversal at every level of the recursion. The fast cursor starts one node ahead and takes both of its steps before the slow cursor takes any, which is how the split lands on the earlier middle rather than the later one.

SimulationMeasuring a random generator's period

A pseudorandom generator is a pure function from state to state, so its output must eventually repeat, and how long that takes is the property you check before seeding a simulation with it. For a small-state generator such as an LCG or xorshift32 the period runs into billions, far too long to store the stream and look for a duplicate, yet two copies of the generator, one stepped twice for every single step of the other, measure it exactly in two words of memory. It is also how a generator seeded into a short orbit gets caught before it quietly repeats itself a few thousand draws in.

Developer toolsReading the end of a stream you cannot rewind

tail -n 5 on a pipe cannot seek backwards and does not know how many lines are coming, which is the same shape as removing the nth node from the end of a list. The answer is the same too: keep a second cursor a fixed n behind the one doing the reading, so the moment the lead hits the end the trailing one is already parked on the node you want. Python's collections.deque(maxlen=n) is that fixed gap turned into a data structure.

Why it works this way

Why two steps and one, and not three and one?

With fast on two and slow on one, the distance between them changes by exactly one every step, so once both are inside the loop that distance has to pass through zero and the pointers land on the same node within a single lap, wherever each of them started. Three steps to one changes the distance by two, and that can step over zero forever: start fast one node ahead, a common variant of the setup, and the gap stays odd, so on a loop of even length the two pointers never meet. Starting both at the head happens to avoid that case, but a second reason survives it. Finding the loop entry needs fast to have walked exactly twice as far as slow, and at three steps to one the meeting point no longer sits where that argument puts it.

Why restarting at the head lands exactly on the entry

Call the run-up before the loop m nodes and the loop itself L nodes, and say the pointers meet k steps into the loop. Slow has walked m + k, fast has walked twice that, and fast's extra distance is a whole number of loops, so m + k is a multiple of L. Walking m more steps from the meeting point therefore lands back on the entry, which is why a pointer released from the head and a pointer released from the meeting point, both moving one step at a time, collide there and nowhere else.

On an even list this returns the second middle

For six nodes the loop above stops with slow on index 3, the later of the two middles. Testing fast.next and fast.next.next instead stops it on index 2, the earlier one. The difference matters when you split a list for merge sort as head..slow and slow.next..end: with the later middle a two-node list splits into the whole list plus an empty one, the recursion never shrinks, and it runs forever. The same condition is also the null guard, because on even lengths fast becomes null rather than landing on a final node, and code that checks fast alone and then reaches for fast.next.next is the usual crash.

Why not just remember every node you have seen?

A set of visited nodes finds the loop in one pass too and is easier to argue about. It costs a slot per node, which is fine for a list you already hold in memory and useless everywhere else. When the sequence is produced by a function rather than stored, such as a generator's state or x -> x * x + c mod n, there are no node identities to put in a set and the space of states is far too large to keep any part of. The two-pointer version is the one that survives when the data is generated instead of held.

Read more

Next up