Find the middle in one pass

Return the middle node of a linked list, and everything after it. When there are two middles, return the second.

Worked example#

For 1 -> 2 -> 3 -> 4 -> 5, the middle is 3, so the answer is 3 4 5.

For 1 -> 2 -> 3 -> 4 -> 5 -> 6 there are two middles, 3 and 4, and the rule says take the second, so the answer is 4 5 6.

Doing it without counting first#

The obvious way is two passes: count the nodes, then walk half of them. That works, and there is a neater way that needs only one.

Move two references at different speeds. The slow one takes one step at a time, the fast one takes two. When the fast one runs off the end, the slow one is exactly halfway.

It works because the fast reference covers twice the distance, so when it has covered all n nodes the slow one has covered n / 2.

The loop condition is where this goes wrong. You need fast and fast.next, because the step ahead reads fast.next.next. Checking only fast crashes on a list of even length.

Why it matters beyond this problem#

The same pair of speeds detects a loop in a list: if there is one, the fast reference eventually laps the slow one and they meet. Being able to say something about a list's shape in one pass with no extra memory is the point of the technique.

The cost#

Time O(n), one pass. Memory O(1).

Constraints#

• 1 <= number of nodes <= 100000
• 1 <= value <= 100