Fast and slow pointers
A list cannot jump to its middle, and counting it first takes a full pass. Instead, send two pointers from the head: slow moves one node at a time, fast moves two. When fast runs out of list, slow has gone exactly half as far.
Find the middle node without counting the list first. Press play or step forward to start.
1function middle(head) {2 let slow = head, fast = head;3 while (fast !== null && fast.next !== null) {4 slow = slow.next;5 fast = fast.next.next;6 }7 return slow;8}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n | fast reaches the end after n steps |
| average | n | one pass, no counting first |
| worst | n | the same for every list |
| space | 1 | just two pointers |
Where it breaks
- Even lengths have two middles. Pick Six nodes: this loop stops on the second middle, the 1. To get the first middle instead, stop when
fast.next.nextis null. - Forgetting the second check. The loop needs both
fast !== nullandfast.next !== null. Drop either andfast.next.nextreads past the end of the list. - The same trick finds cycles. If the list loops back on itself, fast never reaches null. It laps slow and the two land on the same node, which is Floyd's cycle check.