Pattern Recognition Drill
Easy Linked Lists
The Problem
Find the middle node of a linked list.
What approach would you use?
Think about it before scrolling down.
Slow (1 step) and fast (2 steps). When fast hits end, slow is at the middle. One pass, O(1) space.
Common Trap
Counting length then iterating to n/2 works but requires two passes. Slow/fast does it in one.