K-way Merge — Merge k Sorted Lists
↗ LeetCode: Merge k Sorted Lists · Hard · pattern chapter →
Merge k sorted linked lists into one sorted list.
Example 1 — [[1,4,5],[1,3,4],[2,6]] → [1,1,2,3,4,4,5,6]Example 2 — [[]] → []Example 3 — [[1],[2],[3],[4],[5]] → [1,2,3,4,5]
Constraints — k ≤ 10⁴; total nodes N ≤ 10⁴; values -10⁴..10⁴. Naive collect-then-sort is O(N log N) — throws away that inputs are pre-sorted. Sequential merging is O(kN) — at k=N=10⁴ that's 10⁸ ops. Heap merge is O(N log k) ≈ 1.3·10⁵ — 750× faster.
Interview timer00:00
Approach 1 — Collect + sort
Intuition. Walk every list; collect values; sort; rebuild.
ListNode mergeKListsSort(ListNode[] lists) {
List<Integer> all = new ArrayList<>();
for (ListNode l : lists) for (ListNode c = l; c != null; c = c.next) all.add(c.val);
Collections.sort(all);
ListNode dummy = new ListNode(0), tail = dummy;
for (int v : all) { tail.next = new ListNode(v); tail = tail.next; }
return dummy.next;
}Complexity — Time O(N log N); Space O(N). Ignores that inputs are already sorted.
Approach 2 — Merge pairs sequentially
Intuition. Repeatedly merge answer with next list (two-list merge).
ListNode mergeKListsSeq(ListNode[] lists) {
ListNode answer = null;
for (ListNode l : lists) answer = mergeTwo(answer, l);
return answer;
}Complexity — Time O(k · N) (each merge sees up to N nodes); Space O(1). Bad when k is large.
Approach 3 — Divide and conquer (pair-wise merges)
Insight from sequential. Merging pairs symmetrically halves the work per round. log k rounds, each round processes all N nodes → O(N log k).
ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
while (lists.length > 1) {
List<ListNode> merged = new ArrayList<>();
for (int i = 0; i < lists.length; i += 2) {
ListNode a = lists[i];
ListNode b = i + 1 < lists.length ? lists[i + 1] : null;
merged.add(mergeTwo(a, b));
}
lists = merged.toArray(new ListNode[0]);
}
return lists[0];
}Complexity — Time O(N log k); Space O(log k) recursion.
Approach 4 — Min-heap of live heads
Insight from D&C. Instead of merging offline, keep a min-heap of k live heads. Pop the smallest, splice onto the answer, push its .next. Each of the N nodes is popped once → O(N log k).
Trap. Re-feed the heap — after popping a node from list A, immediately offer A.next (or the list is orphaned).
ListNode mergeKListsHeap(ListNode[] lists) {
PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode l : lists) if (l != null) heap.offer(l);
ListNode dummy = new ListNode(0), tail = dummy;
while (!heap.isEmpty()) {
ListNode n = heap.poll();
tail.next = n; tail = n;
if (n.next != null) heap.offer(n.next);
}
return dummy.next;
}Complexity — Time O(N log k); Space O(k). Same time as D&C, but streaming-friendly and easier to reason about.
Try it yourself
Complexity summary
| Approach | Time | Space |
|---|---|---|
| Collect + sort | O(N log N) | O(N) |
| Sequential pairs | O(k · N) | O(1) |
| D&C pairs | O(N log k) | O(log k) |
| Min-heap | O(N log k) | O(k) |
When to use which
- Small k or lists in memory → D&C.
- Streaming or k unknown at start → min-heap.
- k = 2 special case → dummy-head splice (see Merge Two Sorted Lists).
Related problems (same ladder applies)
- Merge Two Sorted Lists — k=2 special case
- Smallest Range Covering Elements from K Lists — heap of one from each list
- Ugly Number II — 3-way merge with dedup
- Kth Smallest Element in a Sorted Matrix — heap of row heads