Find the middle of a linked list in one pass

Question

You receive the head of a singly linked list whose length you do not know in advance. You cannot walk it, count, then walk again cheaply if it is a huge on-disk list, and you may only traverse forward.

1 -> 2 -> 3 -> 4 -> 5      middle is 3
1 -> 2 -> 3 -> 4           middle is 3 (return the second of the two)

Return the middle node in one pass using $O(1)$ extra space.

Accepted Answer

Use the same slow and fast pointer trick that powers cycle detection, but without a cycle. Advance slow one node per step and fast two nodes per step. When fast runs off the end, slow has covered exactly half the distance, so it sits on the middle. Odd length 1 - 2 - 3 - 4 - 5: slow visits 1, 2, 3 while fast visits 1, 3, 5; fast.next is None, so we stop with slow on 3, the true middle. Even length 1 - 2 - 3 - 4: slow visits 1, 2, 3 while fast visits 1, 3, then None; we stop with slow on 3, the second of the two central nodes. To return the first middle instead, stop when fast.next.next is Non…

Find the middle of a linked list in one pass

Your answer

More Coding questions