RavnaryA Knowledge Platform
Colour theme

Card 01/ 08

Take the quiz

ConceptDifficulty: Intermediate3 min

Fast and Slow Pointers: Two Speeds Through One List

One pointer moves one node at a time and the other moves two, so when the fast one reaches the end the slow one is halfway.

Fast and slow pointers walk one list at two speeds: slow moves one node a move and fast moves two, and where slow is when fast stops answers the question. The cue is a property of the problem: the input is a linked list, or any sequence with no index and no known length, the question is about its middle, its end or a repeat, and the extra memory has to be O(1). A linked list is a chain of nodes, each holding a value and a reference, next, to the node after it, and the Linked Lists topic in Data Structures builds one.

The pattern keeps one invariant: after k moves, slow has gone k nodes and fast 2k. So when fast cannot take another two steps, slow has gone half as far, which is the middle. The loop runs while fast and fast.next both exist, because fast needs both to move twice. On 10 20 30 40 50 60 both start on 10.

Which value is slow on when fast can no longer move?
  1. Fast moves from 10 to 30, then to 50, then past the end after 60, so slow takes three moves: 20, 30, 40.

The trace follows both pointers move by move, with each value one cell in list order.

Slow and fast on 10 20 30 40 50 60

Input10 → 20 → 30 → 40 → 50 → 60 → null

  1. Start: both on 10

    1. 10slowfast
    2. 20
    3. 30
    4. 40
    5. 50
    6. 60

    Both pointers start on the head

  2. Move 1: slow 20, fast 30

    1. 10
    2. 20slow
    3. 30fast
    4. 40
    5. 50
    6. 60

    Slow takes one step and fast takes two

  3. Move 2: slow 30, fast 50

    1. 10
    2. 20
    3. 30slow
    4. 40
    5. 50fast
    6. 60

    Fast is on 50, and 50 has a next node, so the loop runs again

  4. Move 3: slow 40, fast past the end

    1. 10
    2. 20
    3. 30
    4. 40slow
    5. 50
    6. 60

    Fast steps past 60 to null, so the loop stops with slow on 40

ResultSlow stops on 40, the second of the two middles.

A list of six values has two middles, 30 and 40, and this loop gives the second. On an odd list, such as 1 2 3 4 5, fast stops on the last node and slow is on the one true middle, 3. A loop that must give the first middle of an even list runs while fast.next and fast.next.next exist instead, and the choice decides where a list splits in two: the wrong one shifts the split by a node with no error. Either way the walk is O(n) time for n nodes and O(1) extra space, where copying the values into an array to index the middle costs O(n) space.

Two runners on a track, one twice as fast as the other, work the same way: on a straight road the fast one finishes when the slow one is halfway, and on a looped track the fast one laps the slow one. The likeness breaks at how they move. Runners move continuously and could pass each other without ever being level, while pointers move in whole nodes, and inside a loop fast gains exactly one node a move, which is what makes a meeting certain.

← → move through sections and cards