Middle of the Linked List

Easy#876middle

You get the head of a linked list. Return its middle node. When the length is even there are two middle nodes, and the answer is the second of them. Our example: 5 → 2 → 7 → 4 → 9 → 1 → 6 → 3, eight nodes — the middle nodes are 4 and 9, so the answer is the node 9.

876 Middle of the Linked ListWalkthrough · 1×

Example: the list 5 → 2 → 7 → 4 → 9 → 1 → 6 → 3, eight nodes.

head52749163noneslow
slowfastthe middle

slow = head, node 5

01/16
restart · back · play · step
Speed
1function middleNode(head):
2 slow = head
3 fast = head
4 while fast and fast.next are not none:
5 slow = slow.next
6 fast = fast.next.next
7 return slow
state
slow
5
fast
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Every round fast walks two steps and slow one, so fast is always twice as far from the head as slow. When fast runs out of list, slow has covered half of it.
  2. With an even length fast stops on none, after n / 2 rounds: slow is then on node n / 2 + 1, the second middle. With an odd length fast stops on the last node and slow is on the only middle.
  3. The length is never counted: one pass, and the loop condition alone decides when to stop.

Complexity

Time O(n): fast walks the list once, two nodes a round, and slow walks half of it. Memory O(1): two pointers.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.