Fast & Slow Pointers

Beginner · 16 min read · Problem-Solving Patterns, Linked Lists

Cycles, middles and the k-th from the end with two runners at different speeds.

Linked lists take away the thing arrays give you for free: you can't jump to the middle or look at "the 3rd node from the end" — you can only walk forward. Two pointers moving at different speeds (or with a fixed gap) recover most of what you lost, in one pass and O(1) memory.

The middle: fast moves twice as fast

When fast reaches the end, slow has gone half as far — it's in the middle.

Cycles: Floyd's tortoise and hare

Step through it on a list drawn in its real shape, a ρ: a straight tail leading into a loop. The highlighted arrows are the moves just made (one for slow, two for fast). Once both are on the loop, the step tells you how far fast is behind slow, and that gap shrinks by one each step.

The k-th from the end: a fixed gap

Move a lead pointer n steps ahead, then move both until lead hits the end. lag is now n from the end. A dummy node in front of the head handles removing the head itself without a special case.

Worked problems beyond lists

Find the middle, reverse the second half (see In-Place Reversal), then compare the halves.

Practice ladder

Interview questions

Why do the fast and slow pointers always meet if there is a cycle?
How would you detect a cycle if O(n) extra space were allowed? Why prefer Floyd's algorithm?

Key takeaways

Speed 1 vs speed 2: the middle, and cycle detection in O(1) space.
Floyd phase 2: restart one pointer at the head; both at speed 1 meet at the cycle entrance.
A fixed gap finds the k-th from the end; a dummy node removes special cases at the head.
"Next = f(current)" sequences and "values are indexes" arrays are hidden linked lists.

Previous: Cyclic Sort · Next: In-Place Reversal & Dummy Nodes