Finding the Middle Node
You'll learn how to find the exact center of a linked list in a single, efficient pass using a clever two-pointer technique.
The Core Idea
When working with linked lists, you can't just jump to the middle like you can with arrays—you have to traverse node by node. The naive approach would be to count all nodes first, then traverse halfway. But there's a smarter way: use two pointers moving at different speeds.
The Two-Pointer (Slow and Fast) Technique
Imagine two runners on a circular track. One runs at normal speed (slow pointer), the other runs twice as fast (fast pointer). When the fast runner completes the lap, the slow runner will be exactly halfway around.
Apply this to linked lists:
- Start both pointers at the head
- Move
slowone node at a time - Move
fasttwo nodes at a time - When
fastreaches the end,slowis at the middle
Why it works: If fast moves twice as quickly and they start together, by the time fast reaches the last node (or falls off the end), slow has covered exactly half the distance.
Example: 1 → 2 → 3 → 4 → 5 → NULL
Step 0: slow=1, fast=1
Step 1: slow=2, fast=3
Step 2: slow=3, fast=5
Step 3: slow=3, fast=NULL (done!)
The middle node is 3.
Edge Cases
- Even-length lists: Convention typically returns the second middle node
- Single node: That node is the middle
- Empty list: Handle the NULL case before starting
Key Takeaway: The two-pointer technique finds the middle node in one pass with O(n) time and O(1) space by moving a fast pointer twice as quickly as a slow pointer.