visual walkthrough
Middle of the Linked List
Fast/slow to find the midpoint, a sub-step of many problems.
The idea
A list can't jump to its middle: you only know where the middle is once you know the length.
Or let a second pointer measure it for you: move fast two steps for every one step of slow. When fast runs out of list, slow is exactly halfway.
Complexity
| approach | time | space |
|---|---|---|
| Count, then walk | O(n) | O(1) |
| Slow and fast pointers | O(n) | O(1) |