Merge k Sorted Lists
Problem statement
You get an array of k linked lists, lists, where every individual list
is already sorted in ascending order. Merge all of them into one single
sorted linked list, and return it.
Think of each list as one host's sorted stream of timestamped events, and the goal is to produce a single, correctly time-ordered feed across every host — the same problem as merging two sorted lists (a well-known building block), but generalized to any number of them at once.
Examples
Example 1
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The three lists are 1→4→5, 1→3→4, and 2→6. Merged together in sorted order, the smallest remaining value across all three lists is picked one at a time: 1 (from the first list), then 1 (from the second list), then 2, then 3, then 4 (either list), then 4 (the other list), then 5, then 6.
Example 2
Input: lists = []
Output: []
Explanation: There are no lists at all (k = 0), so there's nothing to merge and the result is an empty list.
Example 3
Input: lists = [[]]
Output: []
Explanation: There is one list, but it's empty. Merging a single empty list still produces an empty result.
Hints
Approach
Optimal: Min-heap of list heads
Intuition
At any point during a merge, the only nodes that could possibly be "next" are the current front node of each list that still has nodes left — there are never more than k candidates to consider at once. Instead of comparing all of them one by one every single step (which is part of why the better approach's repeated pairwise merges cost more), keep them in a min-heap keyed by value. Popping the heap's minimum instantly gives the smallest candidate across every list. After using that node, push whatever comes after it in its own list (if anything) back onto the heap, since that's now a new candidate. This keeps the heap's size bounded by k throughout, so each step only costs O(log k) instead of comparing k values directly.
Steps
- Push the head node of every non-empty list onto a min-heap, keyed by node value.
- While the heap isn't empty: pop the node with the smallest value.
- Attach that node to the end of the result list being built.
- If the popped node has a
nextnode in its own original list, push thatnextnode onto the heap. - Repeat until the heap is empty, then return the head of the built result.
Dry run
lists = [[1,4,5],[1,3,4],[2,6]] — the three list heads are 1 (list A), 1
(list B), 2 (list C)
| pop | value | attach | push next |
|---|---|---|---|
| 1 | 1 (A) | result: 1 | push 4 (A's next) |
| 2 | 1 (B) | result: 1,1 | push 3 (B's next) |
| 3 | 2 (C) | result: 1,1,2 | push 6 (C's next) |
| 4 | 3 (B) | result: 1,1,2,3 | push 4 (B's next) |
| 5 | 4 (A or B — tied) | result: 1,1,2,3,4 | push that list's next (5 or, if B was taken, nothing left for B) |
| 6 | 4 (the other tied one) | result: 1,1,2,3,4,4 | push its next if any |
| 7 | 5 (A) | result: 1,1,2,3,4,4,5 | A now exhausted |
| 8 | 6 (C) | result: 1,1,2,3,4,4,5,6 | C now exhausted, heap empty |
Final result: 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6 — the same answer as both
earlier approaches, with the heap never holding more than 3 nodes (one per
list) at any moment.
Edge cases: an empty lists array never pushes anything onto the heap, so
the while loop never runs and the result stays empty (example 2). A list
that is itself empty (example 3) is simply skipped when populating the
initial heap, since only non-null heads are pushed. When two nodes tie in
value (like the two 4s here), a stable tie-break (Python's tuple ordering,
an explicit index tie-breaker, or the language's own stable comparison) is
needed so the heap doesn't try to compare the linked-list nodes directly —
this is why the Python code below pairs each node with an index in the
heap entry.
Complexity
Time O(N log k) - every one of the N nodes is pushed onto the heap and popped from it exactly once, and each push or pop costs O(log k) since the heap never holds more than k nodes at a time (one per still-active list).
Space O(k) - for the heap itself (one node per list, at most), on top of O(1) extra for rewiring nodes — no new nodes are allocated, same as the better approach.
import heapq
from typing import List, Optional
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
heap = []
for i, node in enumerate(lists):
if node:
# (value, a tie-breaker index, the node) -- the index avoids
# comparing ListNode objects directly when values tie.
heapq.heappush(heap, (node.val, i, node))
dummy = ListNode()
cur = dummy
while heap:
val, i, node = heapq.heappop(heap)
cur.next = node
cur = cur.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
if __name__ == "__main__":
def build(vals):
dummy = ListNode()
cur = dummy
for v in vals:
cur.next = ListNode(v)
cur = cur.next
return dummy.next
def to_list(node):
out = []
while node:
out.append(node.val)
node = node.next
return out
sol = Solution()
print(to_list(sol.mergeKLists([build([1, 4, 5]), build([1, 3, 4]), build([2, 6])])))
print(to_list(sol.mergeKLists([])))
print(to_list(sol.mergeKLists([build([])])))RecapThe whole problem in a few lines, for the night before
- Spot it: k sorted lists (or arrays) that must become one sorted list
- Idea: keep a min-heap with the current head of each list; pop the smallest, then push that node's next
- Cost: O(N log k) time for N total nodes, O(k) space for the heap
- Trap: on equal values Python compares the nodes and crashes, so put the list index in the tuple; skip empty lists
Interview follow-ups
The k lists are actually stored across k different machines, and you can only fetch one node at a time from each over the network.
The heap approach generalizes directly: instead of holding the actual
nextnode locally, hold a placeholder representing "the next value from machine i", fetched over the network only when that machine's previous value has just been consumed and pushed as the new candidate. This keeps the number of in-flight network requests bounded by k (the same as the heap's size), rather than needing to fetch every value up front.What if k could be enormous — say, a million lists, most of them very short?
The heap approach's O(N log k) already handles this reasonably, since
log kgrows very slowly even for huge k, but building the initial heap of a million entries still costs something. A common refinement is a divide-and-conquer merge: pair up the lists and merge each pair, then pair up those results and merge again, halving the number of "active" lists at each round until one list remains. That still costs O(N log k) overall, but avoids ever holding all k list heads in one heap simultaneously, spreading the work more evenly across rounds instead.
Frequently asked questions
k (the number of lists) and log k behave very differently as k grows.
With, say, 1,000 lists, k is 1,000 but log₂ k is only about 10 — so the
heap approach does roughly 100 times less comparison work overall than the
pairwise-merge approach in that case. The gap widens the more lists there
are; with only 2 or 3 lists, the two approaches are much closer in cost.
Python's heap compares whatever you push directly, and ListNode objects
don't define an ordering (there's no built-in way to say one node is "less
than" another) — comparing two nodes directly would raise an error the
moment two values tie and Python needs a tiebreaker. Including the value
first makes the heap sort by value as intended; including a unique index
second means Python never needs to compare the ListNode objects
themselves, since the index alone is already enough to break any tie
before it gets there. Java's and C++'s heaps instead take an explicit
comparator that only looks at .val, so they don't hit this problem.
The better approach is worth knowing because it needs no extra data structure beyond what merging two lists already needs, and for a small number of lists (or in a setting where a heap isn't readily available) it's simpler to write correctly under pressure. In an interview, showing the better approach first and then explaining why a heap improves on it (the O(N·k) vs O(N log k) comparison above) demonstrates the same kind of reasoning the optimal approach itself is testing for.
Merging several independently sorted streams into one ordered stream is a common building block — combining sorted, timestamped log shards from several hosts into one global timeline, or merging sorted result pages from several database replicas into one final ranked list, both reduce to this exact problem.
