Find the middle without counting
Find the middle of a chain in one walk by sending a fast pointer two steps at a time beside a slow pointer that goes one. About 12 minutes.
A race along the chain
You can find the middle of a list by counting it, then walking halfway. That takes two walks. Here is a trick for one: start two runners at the head. One steps one node at a time, the other steps two. When the fast one reaches the end, the slow one has covered only half the distance.
The slow runner is then standing in the middle. For a list with two middle nodes, it lands on the second.
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slowBoth runners start at the head, node 1.
When to stop
The fast runner takes two steps, so it needs both the node it stands on and the one after to exist. If the list has an odd number of nodes, fast ends exactly on the last node, and fast.next is nothing. If the list is even, fast falls off the end and is nothing.
Checking both fast and fast.next in the loop condition covers both cases, and also an empty list, where slow stays on nothing.
A list has 4 nodes: 1, 2, 3, 4. Where does slow end up?
- AOn node 3, the second of the two middle nodes
- BOn node 2
- COn node 4
Show the answer
On node 3, the second of the two middle nodes. Fast falls off the end after two rounds, when slow has moved two nodes.
Middle of the list
Given the head of a singly linked list, return the middle node. If the list has two middle nodes, return the second one. Because a node carries the rest of the list with it, the answer is shown as the list that starts at that node.
head = [1, 2, 3, 4, 5] → [3, 4, 5]
0 ≤ number of nodes ≤ 5,000 · -1,000,000 ≤ node.val ≤ 1,000,000