Return the value of the middle node. For an even-length list, return the second of the two middle nodes. Assume a non-empty list.
middleValue(head)
Input format: space-separated node values.
1 → 2 → 3 → 4 → 5 // → 3
1 → 2 → 3 → 4 // → 3 (second middle)
7 // → 7
The obvious way to find the middle: count the nodes, then walk halfway. That touches the list twice — once to count, once to reach the middle. Can you find it in one pass, without knowing the length ahead of time?
Two runners start together, one running twice as fast. By the time the fast one finishes the track, the slow one has covered exactly half. Advance 'slow' one step and 'fast' two steps each iteration. When fast runs out of track, slow sits at the midpoint — it covered exactly half the distance fast did.
Start both at the head, loop while fast and the node after it both exist, advancing fast by two and slow by one. For odd-length lists, fast lands exactly on the last node when the loop stops, and slow is at the true middle. For even-length lists, fast runs one step past the end, and slow lands on the second of the two middle nodes — exactly what's asked. Not a coincidence to memorize — it falls directly out of fast covering twice slow's distance; tracing a 4-node and 5-node example by hand confirms it.
This tortoise-and-hare pattern solves it in one pass — O(n) time, O(1) space — versus count-then-walk's two passes. It's also foundational for a family of linked-list problems (cycle detection, cycle start, splitting a list in half) that all lean on the same "one pointer moves twice as fast" idea.
def middle_value(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slow.val
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.