Middle of the Linked List
Return the middle node of a singly linked list. If there are two middles, return the second.
Open on LeetCode ↗Intuition
Run two pointers, one twice as fast as the other. When the fast pointer reaches the end, the slow one — moving at half speed — sits exactly at the middle.
Approach
The two-pass version, and why one pass is possible
The straightforward way is to walk the list once to measure its length, then walk again to position length // 2. It's correct but takes two passes — and a singly linked list gives us no random access, so the second walk is unavoidable unless we find the middle without ever knowing the length.
Race two pointers at different speeds
Let a fast pointer move two nodes for every one node the slow pointer moves. When fast falls off the end, it has covered the whole list; slow, going half as fast, has covered exactly half — so it's sitting on the middle. We learned the midpoint relative to the end without ever computing the length.
Loop on fast and fast.next
Advance slow by 1 and fast by 2 while both fast and fast.next exist (so the double step is safe). Return slow. For an even-length list this naturally lands on the second of the two middles, which is what the problem asks. Single pass, O(n) time, O(1) space.
Solution & live demo
Edge cases
fast stops at null after node 4; slow is at node 3 — the second of the two middles, as required.
The loop condition fails immediately; slow stays at the head and is returned.
One iteration moves slow to the second node, which is the correct middle.