Fast & Slow Pointer

Fast and slow pointer is a two-pointer pattern for structures that are easy to traverse but expensive to index. The usual setup starts slow and fast at head. On each iteration, slow advances one step and fast advances two steps, as long as fast can safely move.

Because fast covers distance twice as quickly, the relationship between the two pointers reveals structure. When fast hits the end of 1 -> 2 -> 3 -> 4 -> 5 -> null, slow is at the middle. If fast ever catches slow inside a list, the list contains a cycle.

The middle-node template moves slow by one and fast by two while fast != null and fast.next != null. When the loop ends, slow is at the middle. For odd length, it lands on the exact middle. For even length, this common version lands on the second middle.

The invariant is distance. After t loop iterations, slow has moved t steps and fast has moved 2t steps. When fast has consumed the list, slow has consumed about half of it without a separate length pass.

Floyd's cycle detection uses the same speed difference. In an acyclic list, fast eventually reaches null. In a cyclic list, fast keeps looping and gains one node per iteration on slow inside the cycle, so the two pointers must eventually meet.

The meeting point proves a cycle exists; a second phase can find the cycle entry by moving one pointer back to head and then advancing both one step at a time. They meet at the first node in the cycle because the distances align modulo the cycle length.

A related two-pointer version finds the k-th node from the end. Move fast exactly k steps ahead, then move slow and fast together until fast reaches null. The fixed gap means slow is now k nodes from the end.

This is the same idea in a different form: encode position information as a distance between pointers rather than as an index. It is especially useful when the list length is unknown or when a one-pass solution is required.