Fast and Slow Pointers

Two references, different speeds

The fast and slow pointers technique uses two references that start in the same chain but move at different speeds. The slow pointer usually advances by one node, while the fast pointer advances by two. The difference in distance traveled reveals information about the list structure without an index array and without an extra pass to count the length.

Finding the middle of a list

While the fast pointer moves two nodes at a time, the slow pointer moves one. When the fast pointer reaches the end, the slow pointer is roughly in the middle.

Node slow = head;
Node fast = head;

while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}

Node middle = slow;

Both pointers only move forward, so the algorithm runs in O(n) and uses O(1) additional memory. For an even number of nodes, this version leaves slow on the second of the two middle nodes.

Why the technique works

After every loop iteration, fast has traveled roughly twice as many nodes as slow. So when the fast pointer has exhausted the entire list length, the slow pointer has covered about half of it.

This idea is useful for more than finding the middle. Different movement speeds let us compare the positions of two references inside the same chain, and in the next topic it becomes the basis for working with a list that has no ordinary end.