Merge K Sorted Lists
Merge k sorted linked lists into one sorted list.
- k == lists.length
- 0 <= k <= 10⁴
- 0 <= lists[i].length <= 500
- -10⁴ <= lists[i][j] <= 10⁴
- lists[i] is sorted in ascending order.
- The sum of lists[i].length will not exceed 10⁴.
Intuition
Merge k sorted lists combines k sorted linked lists into one sorted list. Concatenating everything and sorting works at O(N log N) for N total nodes, but it throws away the fact that each input is already ordered.
Use that instead. At any moment, the next node of the output must be the smallest among the current heads of the k lists — nothing behind a head can be smaller, because each list is sorted. So the whole problem is repeatedly answering "which of these k values is smallest?".
Scanning all k heads each time gives O(N·k). A min-heap answers the same question in O(log k):
- Pop the smallest head, append it to the output, then push that node's successor.
The heap holds at most k nodes — one per list — so it stays small regardless of how long the lists are. Every node enters and leaves exactly once, giving O(N log k) overall.
One practical detail bites in most languages: list nodes are not comparable, so when two heads hold equal values the heap tries to compare the node objects and raises an error. Push a tuple of (value, tiebreaker, node) where the tiebreaker is the list index or a counter, so equal values are resolved before the node is ever examined.
The alternative is merging pairwise in rounds — merge lists two at a time, halving the count each round. That is also O(N log k), since there are log k rounds each doing O(N) work.
Merging two sorted lists is a pointer comparison; merging k of them is the same idea with a heap deciding which pointer to advance. The general pattern: when you repeatedly need the minimum across k moving frontiers, a heap of size k gives it in O(log k) instead of an O(k) scan. Only the k current heads ever need to be in memory — not the whole input.
Approach
Before reading on: price up what the direct approach costs here, then ask why only the extreme element matters and the rest need no ordering. Aim for O(n log k) time and O(k) space.
Recognise the repeated question
The next output node is always the smallest of the k current heads, since each list is sorted. The whole algorithm is answering that one question efficiently, N times over.
Seed a min-heap with every head
Push the first node of each non-empty list. The heap now holds every candidate for the smallest remaining value, and it will never hold more than k entries at once.
Add a tiebreaker to the heap entry
Push (value, index, node) rather than (value, node). Linked list nodes are not comparable in most languages, so equal values would make the heap compare node objects and throw — the index resolves the tie first.
Pop, append, and replenish
Pop the smallest entry, append its node to the output tail, and push its next if one exists. Each pop finalises exactly one output node, and each push keeps that list represented in the heap.
Use a dummy head for the output
Build the result behind a dummy node so appending never needs a null check on the first insertion. Return dummy.next at the end — the same pattern that simplifies most linked-list construction.
Know the pairwise alternative
Merging lists two at a time in rounds halves the count each pass, giving log k rounds of O(N) work — also O(N log k). The heap version streams the answer and is easier to adapt when lists arrive dynamically.
Cost of the heap merge
Each of the N nodes is pushed and popped once at O(log k), giving O(N log k) time and O(k) space for the heap. Compare with concatenate-and-sort at O(N log N) — the saving matters when k is far smaller than N.
Solution & live demo
Common pitfalls
Putting nodes in the heap without a tiebreaker
heap = [(node.val, node) for node in lists if node]
heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
When two nodes share a value, Python falls through to comparing the second tuple element — and ListNode defines no <, so it raises TypeError. The list index is unique, so it settles ties before any node comparison happens.
Pushing every node upfront
heap = [(n.val, i, n) for i, l in enumerate(lists)
for n in iterate(l)]heap = [(node.val, i, node) for i, node in enumerate(lists) if node] # push each successor only as its predecessor is popped
That's O(N) space for N total nodes and turns each operation into O(log N). Holding only the k list heads keeps the heap at size k, so space is O(k) and each push is O(log k).
Returning dummy instead of dummy.next
return dummy
return dummy.next
dummy is a placeholder node holding value 0 that exists only so tail has something to attach to on the first iteration. It is not part of the answer — the real head is whatever got linked after it.
Edge cases
Empty lists never enter the heap; all-empty returns None.
The (val, idx) tuple breaks ties deterministically.