The problem
You are given k linked lists, each sorted. Merge them all into one sorted list.
Input: [1,4,5], [1,3,4], [2,6] Output: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6
Picture it
Picture k sorted trains waiting on parallel tracks and one dispatcher. At each moment the dispatcher sends out the smallest front coach among all tracks. To find that smallest coach instantly, the front coaches sit in a min-heap (a priority queue). After sending one out, the next coach on that same track joins the heap.
How to recognise it
- You have many sorted sequences and need one sorted output, or the next smallest item across all of them.
- At every moment the next item is the smallest of the k fronts. Only the fronts matter; nothing deeper in a list can be smaller than its own front.
- You need "give me the minimum, then replace it with another item" over and over. That is what a min-heap (a priority queue: a structure that returns its smallest item in O(log k) and accepts a new one in O(log k)) is built for.
- k can be large (LeetCode allows 10^4 lists), so scanning all fronts for every node is expensive.
Start with brute force
Keep the current front of each list. To pick each next node, scan all fronts for the smallest, link it, and advance that list.
def merge_k_brute(lists):
heads = [l for l in lists if l]
dummy = tail = Node(0)
while heads:
best = min(range(len(heads)), key=lambda i: heads[i].val)
tail.next = heads[best]
tail = tail.next
if heads[best].next:
heads[best] = heads[best].next
else:
heads.pop(best)
return dummy.next
Each of the N nodes costs a scan of up to k fronts, so time is O(N · k) and extra space O(k). LeetCode allows k = 10^4 lists and N = 10^4 nodes in total, which is up to about 10^8 comparisons. (Collecting all values and sorting them, O(N log N), is faster but builds new nodes and ignores that the lists are sorted.)
From brute force to the idea
- Find the waste. Each scan looks at k fronts, but only one front changed since the last scan. Everything else is compared again for nothing.
- Keep the fronts in a heap. Put
(value, list index, node)for each non-empty list into a list and callheapify, which arranges it as a min-heap in O(k). - Pop the smallest, push its successor.
heappopgives the smallest front in O(log k). Link it to the tail. If that node has anext, push it: it is the new front of the same list. - Why the list index is there. Python compares tuples item by item. When two values are equal it compares the second item; without the index it would compare two
Nodeobjects and raiseTypeError. Each list has only one node in the heap at a time, so the index alone always breaks a tie. - Stop when the heap is empty. Every node has been linked exactly once. A dummy node again avoids a special case for the first one.
This is the key idea: a min-heap of the k current fronts, so each next node costs O(log k) instead of O(k).
Merging the lists in pairs (1 with 2, 3 with 4, and so on, then again) also reaches O(N log k) without a heap.
The key idea
A min-heap of the k front nodes gives the next smallest in O(log k): total O(N log k).
Python solution
def merge_k(lists):
heap = [(l.val, i, l) for i, l in enumerate(lists) if l]
heapify(heap)
dummy = tail = Node(0)
while heap:
val, i, node = heappop(heap)
tail.next = node
tail = node
if node.next:
heappush(heap, (node.next.val, i, node.next))
return dummy.nextLeetCode adds the imports for you. To run this on your own machine, put this at the top: from heapq import heappush, heappop, heapify
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(N · k): a scan of up to k fronts for each of the N nodes | O(k): the list of fronts |
| Min-heap (shown code) | O(N log k): one pop and at most one push per node, on a heap of at most k entries, plus O(k) for heapify | O(k): the heap; nodes are relinked, not copied |
Edge cases
- No lists (
[]) or only empty lists ([None, None]): the heap starts empty and the code returnsNone. - One list: its nodes come out in their original order.
- Equal values in different lists (
[1 → 4 → 5, 1 → 3 → 4, 2 → 6]): ties are broken by list index, so the 1 from list 0 comes first. The result is1 → 1 → 2 → 3 → 4 → 4 → 5 → 6. - Very uneven lengths: fine; a list leaves the heap when its last node is popped.
- Imports: the shown code needs
from heapq import heapify, heappop, heappush.
Common mistakes
- Pushing
(val, node)without a tie-breaker, which raisesTypeErroras soon as two fronts have equal values. - Pushing every node of every list at the start. It works, but the heap holds N entries, so time becomes O(N log N) and space O(N).
- Merging the lists one after another into a growing result. Each merge re-walks the result, which costs O(N · k) in the worst case.
- Forgetting to skip empty lists when building the heap, so
l.valis read onNone.
Given k sorted Python lists of numbers, return one sorted list of all their values. For [[1, 4, 5], [1, 3, 4], [2, 6]] the answer is [1, 1, 2, 3, 4, 4, 5, 6]. Describe your approach, then write it if you like.
Compare with our answer
Same heap of fronts, but an array has no next pointer, so each heap entry also stores the position inside its array. After popping (value, i, j), push element j + 1 of array i if it exists.
from heapq import heapify, heappop, heappush
def merge_k_arrays(arrays):
heap = [(a[0], i, 0) for i, a in enumerate(arrays) if a]
heapify(heap)
out = []
while heap:
val, i, j = heappop(heap)
out.append(val)
if j + 1 < len(arrays[i]):
heappush(heap, (arrays[i][j + 1], i, j + 1))
return out
Time O(N log k), extra space O(k) for the heap plus O(N) for the output.
A strong answer mentions: the (value, array, position) entry, skipping empty arrays, and why the heap never grows beyond k.
1. A service must merge 1,000 sorted log files by timestamp into one stream, using little memory. Which approach fits best?
The heap holds one line per file (O(k) memory) and gives the earliest in O(log k). Sorting everything needs all lines in memory, scanning all files costs O(k) per line, and repeated pairwise merging re-reads the growing result.
2. Why is the shown code O(N log k) rather than O(N log N)?
Each list contributes only its current front, so the heap size is at most k and each pop or push costs O(log k). heapify builds a heap, not a sorted list, and pops still cost O(log k).
3. A learner pushes (node.val, node) tuples, without the list index. Which input raises a TypeError?
With two equal first items, Python compares the second items, two Node objects, which have no ordering. A single list has only one entry in the heap at a time, so its equal values are never compared with each other.
Score 60% or more and the lesson is marked complete.