Sort List

Medium#148merge sort

You get the head of a singly linked list of numbers. Sort it in increasing order and return the new head, ideally in O(n log n) time. Our list: 8 → 3 → 5 → 1 — the answer is 1 → 3 → 5 → 8.

148 Sort ListWalkthrough · 1×

Example: sort the linked list 8 → 3 → 5 → 1 with merge sort: find the middle with slow and fast, cut, sort the halves, merge.

8351
waiting on the call stackcurrent call, or the node just linkedsortedmerged list, not filled yetalready merged upwards

sortList([8, 3, 5, 1]): 4 nodes, so split it

01/47
restart · back · play · step
Speed
1function sortList(head):
2 if head is none or head.next is none:
3 return head
4 slow = head
5 fast = head.next
6 while fast is not none and fast.next is not none:
7 slow = slow.next
8 fast = fast.next.next
9 right = slow.next
10 slow.next = none // cut the list after slow
11 left = sortList(head)
12 right = sortList(right)
13 return merge(left, right)
14
15function merge(a, b):
16 tail = dummy // a spare node in front of the result
17 while a and b are not none:
18 link the smaller head behind tail, step on
19 tail.next = whichever of a and b is left
20 return dummy.next
state
head
8
slow
–
fast
–
left
–
right
–
a
–
b
–
click a step to go back

← → step · space play/pause

Why it works

  1. fast moves twice as far as slow, so when fast runs out, slow stands at the end of the first half: the middle is found without an index or a count.
  2. slow.next = none makes the two halves separate lists, so each one is sorted by the same function on its own.
  3. merge takes the smaller head each time and relinks it behind tail; once one list runs out, the rest of the other is already sorted and larger, so it joins with one link.

Complexity

Time O(n log n): halving gives log n levels, and on each level finding the middles and merging pass every node a constant number of times. Memory O(log n): the call stack; the nodes are relinked, not copied.

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.