How Do Slow and Fast Pointers Measure a Linked List?
Runner pointers turn relative movement into distance: one-and-two-step speeds find a middle, while a fixed head start finds a node from the end.
A linked list has no constant-time index jump. Two references can still encode distance by how they move. For the middle, slow moves one edge while fast moves two. For the nth node from the end, fast first opens a gap of exactly n edges.
Finding the second middle
Press Run to execute this example. Use console.log to print a value.
After k iterations, slow has advanced k edges and fast has advanced 2k edges. When fast reaches the end, slow is halfway through. The loop condition makes an even-length list return the second middle: [1, 2, 3, 4] returns 3.
For nth from the end, reject n < 1, advance fast exactly n times, then move both references until fast is null. The invariant is that fast stays n edges ahead, so slow is the requested node when that gap reaches the end.
Complexity, TypeScript, and edges
Both walks take O(n) time and O(1) extra space. The node references—not the input array used to construct a teaching list—must drive the answer.
- Empty input has no middle.
- One node is its own middle.
- Define first or second middle for even lengths before coding.
- If fast becomes null during the head start,
nexceeds the length. - Optional chaining can hide an invalid transition; keep the loop guard explicit.
Optional enrichment
Use slow and fast pointers for cycle detection. That problem needs a different proof: if a cycle exists, the faster pointer eventually gains one position per iteration modulo the cycle length.