Merge k Sorted Lists

Hard#23merge k lists

You get k linked lists, each sorted in ascending order; some may be empty. Join all their nodes into one sorted linked list and return its head. Our example: 2 → 6, an empty list, 1 → 4 → 7, 3 → 5 — the answer is 1 → 2 → 3 → 4 → 5 → 6 → 7.

23 Merge k Sorted ListsWalkthrough · 1×

Example: 2 → 6, an empty list, 1 → 4 → 7, 3 → 5. On the left the lists, below the heap and the answer growing after the dummy node.

lists[0]none26lists[1]nonelists[2]none147lists[3]none35heapsmallest on the left—
not reached yetin the heapnode, just poppedlinked into the answer

The heap will hold one node per list, ordered by node.val

01/55
restart · back · play · step
Speed
1function mergeKLists(lists):
2 heap = empty min-heap // ordered by node.val
3 for each head in lists:
4 if head is not none:
5 push head into heap
6 dummy = new node
7 tail = dummy
8 while heap is not empty:
9 node = pop min from heap
10 tail.next = node
11 tail = node
12 if node.next is not none:
13 push node.next into heap
14 return dummy.next
state
heap
[]
head
–
node
–
tail
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Each list is sorted, so the smallest node not yet linked is always the first unused node of some list. The heap holds exactly those, one per list, so its top is the next node of the answer.
  2. An empty list has no head and never enters the heap; a list that runs out pushes nothing, and the heap just gets smaller. Neither needs a special case later.
  3. The dummy node lets the first node be linked like every other one, so tail.next = node is the same line every time; the nodes are relinked, never copied.

Complexity

Time O(N log k) for N nodes in k lists: each node is pushed and popped once on a heap of at most k. Memory O(k) for the heap: the answer reuses the nodes.

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.