Fast and Slow Pointers
The fast and slow pointers technique, sometimes called the tortoise and hare, runs two pointers through a sequence at different speeds. The fast pointer typically moves two steps for every one step of the slow pointer.
What it reveals
The speed gap exposes structure that a single pointer would miss:
- Cycle detection: if a linked list loops, the fast pointer eventually laps the slow one and they meet.
- Middle element: when the fast pointer reaches the end, the slow pointer sits exactly at the midpoint.
- Nth from end: start the fast pointer a fixed gap ahead, then advance both until the fast one finishes.
Because only two pointers are stored, memory stays constant regardless of input size.
Why meeting works
In a loop the gap between the two pointers shrinks by one each step, so they are guaranteed to collide rather than skip past each other.
Key idea
A speed difference between two pointers reveals cycles and midpoints using only constant memory.