These are the notes for DSA episode 23, a classic hard problem. You get k sorted linked lists and must merge them into one sorted list. The obvious way, scanning the front of every list to pick the smallest, costs O(N·k) and times out with 20,000 lists. The fix is a new data structure, the heap (Java's PriorityQueue): it holds one front per list and hands you the smallest in O(log k), so the whole merge is O(N log k) time and O(k) space. We also meet the dummy node, fix three real bugs, and see the divide-and-conquer alternative. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
A courier company has k hubs. Each hub sends a list of parcels already sorted by delivery time: hub A 1, 4, 5, hub B 1, 3, 4, hub C 2, 6. The dispatcher needs one list, earliest first: 1, 1, 2, 3, 4, 4, 5, 6.
Key observation: every hub's list is sorted, so the earliest parcel left anywhere is always at the front of some hub's list, never in the middle. On a festival sale day there are 20,000 pickup points, not 3.
| At the courier company | In the code |
|---|---|
| A hub's sorted parcel list | A sorted linked list |
| The hubs | Node[] lists (k lists) |
| All parcels | N nodes in total |
| The front parcel of a hub | the head of that list |
| The dispatch list | the merged list |
Problem statement
Given an array of k linked lists, each sorted in ascending order, merge them into one sorted linked list and return its head. Re-link the existing nodes; no new nodes are needed.
Input: [1->4->5, 1->3->4, 2->6]
Output: 1->1->2->3->4->4->5->6
Edge cases: no lists (new Node[]{}), lists that are null, a single list, duplicates, negative values. Two sizes matter: k (number of lists) and N (total nodes).
Brute force: scan every front
Look at the front of every list, take the smallest, attach it to the output, advance that list. Repeat until every list is empty. (It's the two-list merge from merge sort, with k fronts.)
static Node bruteMerge(Node[] lists) {
Node dummy = new Node(0), tail = dummy;
while (true) {
int best = -1;
for (int i = 0; i < lists.length; i++)
if (lists[i] != null && (best == -1 || lists[i].val < lists[best].val))
best = i;
if (best == -1) break;
tail.next = lists[best];
tail = tail.next;
lists[best] = lists[best].next;
}
return dummy.next;
}
show(bruteMerge(new Node[]{build(1, 4, 5), build(1, 3, 4), build(2, 6)})) printed 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> null.
The dummy node. dummy is a fake first node. The output always has a tail to attach to, so the very first real node needs no special case. The answer is dummy.next.
The big input: 20,000 lists
int k = 20000, len = 15;
Node[] lists = new Node[k];
Random r = new Random(7);
for (int i = 0; i < k; i++) {
int[] a = new int[len];
for (int j = 0; j < len; j++) a[j] = (j == 0 ? 0 : a[j - 1]) + r.nextInt(1000);
lists[i] = build(a);
}
20,000 random sorted lists of 15 nodes: N = 3 lakh. Result: Time Limit Exceeded.
Why the brute force is slow
N picks, and every pick scans all k fronts: O(N·k). Only one front changed since the last pick, but we compare all of them again.
| k (with N = 3 lakh) | Front checks (N × k) |
|---|---|
| 3 | 9 lakh: instant |
| 1,000 | 3 × 10⁸ |
| 20,000 | 6 × 10⁹: TLE |
"Just copy all values, sort, rebuild" is O(N log N) and passes, but it ignores that each list is already sorted and copies all N values. Interviewers ask you to use the sorted order.
The key insight: a heap hands you the smallest
We need a box that holds k fronts and always gives the smallest, even as fronts are replaced. That is a min-heap. Think of a knockout tournament:
| In a tournament | In a min-heap (PriorityQueue) |
|---|---|
| The champion sits on top | peek(): the smallest, O(1) |
| A new player climbs one path of matches | add(): O(log size) |
| The champion leaves; only his path is replayed | poll(): O(log size) |
| 20,000 players need only ~15 rounds | log₂ 20,000 ≈ 15 |
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(1);
pq.add(4);
pq.add(2);
System.out.println("smallest: " + pq.peek());
while (!pq.isEmpty()) System.out.print(pq.poll() + " ");
Output: smallest: 1 and 1 2 4 5.
The plan: put every list's front in the heap (at most k nodes). Repeatedly poll the smallest node, attach it, and push its next. Each node is pushed once and polled once, each costing O(log k): O(N log k).
Trace on A = 1,4,5 B = 1,3,4 C = 2,6:
| Step | Poll | Push | Heap after | Output |
|---|---|---|---|---|
| start | 1A, 1B, 2C | {1A, 1B, 2C} | ||
| 1 | 1A | 4A | {1B, 2C, 4A} | 1 |
| 2 | 1B | 3B | {2C, 3B, 4A} | 1 1 |
| 3 | 2C | 6C | {3B, 4A, 6C} | 1 1 2 |
| ... | ||||
| end | {} | 1 1 2 3 4 4 5 6 |
The optimal solution in Java
import java.util.*;
public class Main {
static class Node {
int val;
Node next;
Node(int val) { this.val = val; }
}
static Node build(int... a) {
Node head = null;
for (int i = a.length - 1; i >= 0; i--) {
Node n = new Node(a[i]);
n.next = head;
head = n;
}
return head;
}
static String show(Node h) {
StringBuilder sb = new StringBuilder();
for (; h != null; h = h.next) sb.append(h.val).append(" -> ");
return sb.append("null").toString();
}
static Node mergeK(Node[] lists) {
PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> Integer.compare(x.val, y.val));
for (Node h : lists)
if (h != null) pq.add(h);
Node dummy = new Node(0), tail = dummy;
while (!pq.isEmpty()) {
Node min = pq.poll();
tail.next = min;
tail = min;
if (min.next != null) pq.add(min.next);
}
return dummy.next;
}
public static void main(String[] args) {
System.out.println(show(mergeK(new Node[]{build(1, 4, 5), build(1, 3, 4), build(2, 6)})));
System.out.println(show(mergeK(new Node[]{})));
System.out.println(show(mergeK(new Node[]{null, null})));
System.out.println(show(mergeK(new Node[]{build(-3, 0, 7)})));
System.out.println(show(mergeK(new Node[]{build(2, 2), null, build(-1, 2)})));
}
}
Output:
1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> null
null
null
-3 -> 0 -> 7 -> null
-1 -> 2 -> 2 -> 2 -> null
On 20,000 lists (3 lakh nodes) it printed 300000 nodes merged, 238 ms.
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int val;
Node* next;
Node(int v) : val(v), next(nullptr) {}
};
Node* build(const vector<int>& a) {
Node* head = nullptr;
for (int i = (int)a.size() - 1; i >= 0; i--) { Node* n = new Node(a[i]); n->next = head; head = n; }
return head;
}
string show(Node* h) { string s; for (; h; h = h->next) s += to_string(h->val) + " -> "; return s + "null"; }
Node* mergeK(vector<Node*>& lists) {
auto cmp = [](Node* x, Node* y) { return x->val > y->val; }; // ">" makes it a MIN-heap
priority_queue<Node*, vector<Node*>, decltype(cmp)> pq(cmp);
for (Node* h : lists) if (h) pq.push(h);
Node dummy(0);
Node* tail = &dummy;
while (!pq.empty()) {
Node* mn = pq.top(); pq.pop();
tail->next = mn;
tail = mn;
if (mn->next) pq.push(mn->next);
}
return dummy.next;
}
int main() {
vector<Node*> lists = {build({1, 4, 5}), build({1, 3, 4}), build({2, 6})};
cout << show(mergeK(lists)) << "\n";
vector<Node*> none;
cout << show(mergeK(none)) << "\n";
}
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> null and null. Note: C++'s priority_queue is a max-heap by default, so the comparator uses >.
The same solution in Python
import heapq
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
def build(*a):
head = None
for x in reversed(a):
head = Node(x, head)
return head
def show(h):
out = []
while h:
out.append(str(h.val)); h = h.next
return " -> ".join(out + ["null"])
def merge_k(lists):
heap = []
for i, h in enumerate(lists):
if h:
heapq.heappush(heap, (h.val, i, h)) # i breaks ties: Node objects can't be compared
dummy = tail = Node(0)
while heap:
_, i, node = heapq.heappop(heap)
tail.next = node
tail = node
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
print(show(merge_k([build(1, 4, 5), build(1, 3, 4), build(2, 6)])))
print(show(merge_k([])))
print(show(merge_k([None, build(-1, 2)])))
Output:
1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> null
null
-1 -> 2 -> null
heapq is a min-heap. The list index i in each tuple breaks ties between equal values, so Python never tries to compare two Node objects.
Three real bugs
Bug 1: adding null lists to the heap
for (Node h : lists)
pq.add(h);
With {build(1, 4), null, build(2, 3)}:
Exception in thread "main" java.lang.NullPointerException
at java.base/java.util.PriorityQueue.offer(PriorityQueue.java:325)
at java.base/java.util.PriorityQueue.add(PriorityQueue.java:311)
at Main.mergeK(Main.java:26)
at Main.main(Main.java:37)
PriorityQueue refuses null. Fix: if (h != null) pq.add(h);.
Bug 2: forgetting pq.add(min.next)
Output: 1 -> 1 -> 2 -> 6 -> null. Four nodes are lost. The heap only ever saw the three fronts; each attach overwrote the previous node's next, cutting off the rest of its list. Only the last node polled (2) still dragged its old next (6) along.
Bug 3: the comparator (x, y) -> x.val - y.val
With lists {2000000000} and {-2000000000} it printed 2000000000 -> -2000000000 -> null. The subtraction overflows int (4 × 10⁹), so the heap thinks 2 billion is smaller. Fix: Integer.compare(x.val, y.val) (same bug as episode 20).
Another O(N log k) way: divide and conquer
Merge the lists in pairs with the plain two-list merge, like merge sort (episode 17): each round halves the number of lists (log k rounds), and each round touches all N nodes once.
static Node mergeTwo(Node a, Node b) {
Node dummy = new Node(0), tail = dummy;
while (a != null && b != null) {
if (a.val <= b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = (a != null) ? a : b;
return dummy.next;
}
static Node mergeRange(Node[] lists, int lo, int hi) {
if (lo > hi) return null;
if (lo == hi) return lists[lo];
int mid = (lo + hi) / 2;
return mergeTwo(mergeRange(lists, lo, mid), mergeRange(lists, mid + 1, hi));
}
mergeRange(l, 0, l.length - 1) on our hubs printed 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> null. Don't merge one by one (A+B, then +C, then +D ...): the growing result is re-walked every time, which is O(N·k) again.
Complexity
| Approach | Time | Extra space | 20,000 lists |
|---|---|---|---|
| Scan every front | O(N·k) | O(1) | Time Limit Exceeded |
| Copy all values, sort, rebuild | O(N log N) | O(N) | passes, ignores sortedness |
| Merge one by one | O(N·k) | O(1) | slow |
Min-heap (PriorityQueue) |
O(N log k) | O(k) | 238 ms |
| Divide and conquer (pairs) | O(N log k) | O(log k) recursion | fast |
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
pq.add(h) for every list |
NullPointerException in PriorityQueue.offer |
the heap rejects null |
if (h != null) pq.add(h) |
No pq.add(min.next) |
1 -> 1 -> 2 -> 6 -> null |
the heap never sees the rest | push min.next after polling |
(x, y) -> x.val - y.val |
2000000000 -> -2000000000 |
int overflow |
Integer.compare(x.val, y.val) |
return dummy; |
an extra 0 -> at the front |
dummy is a fake node |
return dummy.next |
new PriorityQueue<>() for nodes with no comparator |
ClassCastException (Node is not Comparable) |
the heap can't order nodes | pass a comparator |
C++ priority_queue with < |
largest first | it's a max-heap by default | comparator with > |
Mini project: the festival dispatch board
Each of k warehouses sends parcels sorted by delivery time. Print the first 5 dispatches across all warehouses without merging everything: poll 5 times from the heap.
Node[] hubs = {build(905, 1130, 1400), build(900, 1000), build(915, 1300)};
PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> Integer.compare(x.val, y.val));
for (Node h : hubs) if (h != null) pq.add(h);
for (int i = 0; i < 5 && !pq.isEmpty(); i++) {
Node m = pq.poll();
System.out.print(m.val + " ");
if (m.next != null) pq.add(m.next);
}
It printed 900 905 915 1000 1130. This is the same idea as "the kth smallest across k sorted lists" (practice 3), in O(k + 5 log k).
Practice
- Write the divide-and-conquer version. See
mergeTwo+mergeRangeabove. Why is it O(N log k)? log k rounds, N work per round. - Merge k sorted arrays with a heap.
Solution
Store {value, array index, position} in the heap.
static List<Integer> mergeArrays(int[][] arrs) {
PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> Integer.compare(x[0], y[0]));
for (int i = 0; i < arrs.length; i++)
if (arrs[i].length > 0) pq.add(new int[]{arrs[i][0], i, 0});
List<Integer> out = new ArrayList<>();
while (!pq.isEmpty()) {
int[] t = pq.poll();
out.add(t[0]);
int i = t[1], j = t[2] + 1;
if (j < arrs[i].length) pq.add(new int[]{arrs[i][j], i, j});
}
return out;
}
{{1, 4, 5}, {1, 3, 4}, {2, 6}, {}} → [1, 1, 2, 3, 4, 4, 5, 6].
- The kth smallest value across k sorted lists, without merging everything.
Solution
static int kthSmallest(Node[] lists, int k) {
PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> Integer.compare(x.val, y.val));
for (Node h : lists) if (h != null) pq.add(h);
while (true) {
Node min = pq.poll();
if (--k == 0) return min.val;
if (min.next != null) pq.add(min.next);
}
}
For our hubs and k = 5 it returned 4 (1, 1, 2, 3, 4). O((lists + k) log lists).
- Smallest range covering one number from each list (hard): keep one front per list in a min-heap and track the current maximum; the range is
[heap min, max]. Advance the list that holds the minimum, and stop when any list runs out.
Quick quiz
show(mergeK(new Node[]{build(3), build(1, 2), null}))
3 -> 1 -> 2 -> null1 -> 2 -> 3 -> nullNullPointerException1 -> 3 -> null
Answer
1 -> 2 -> 3 -> null. The null list is skipped by the check; the heap starts with {1, 3}, polls 1, pushes 2, polls 2, polls 3. (Real output: 1 -> 2 -> 3 -> null.)
Interview questions
- Merge k sorted lists: best complexity? O(N log k) time with a min-heap of size k (or divide and conquer).
- Why log k and not log N? The heap never holds more than one node per list, so its size is at most k.
- What is a heap? A complete binary tree stored in an array where every parent is ≤ its children (min-heap);
peekis O(1),add/pollare O(log size). - Why use a dummy node? So attaching the first node isn't a special case; return
dummy.next. - Heap vs divide and conquer? Same O(N log k); the heap uses O(k) extra memory and handles streaming input; pairs use O(1) extra (plus recursion) and no comparator.
- Why is merging one by one slow? The merged list grows, and it is re-walked for each new list: O(N·k).
- How do you make a min-heap in C++ and Python? C++
priority_queuewith a>comparator (orgreater<>); Pythonheapqis already a min-heap. - Your comparator is
a.val - b.val. Problem? Overflow for large values; useInteger.compare.
Glossary
| Term | Meaning |
|---|---|
| k / N | The number of lists / the total number of nodes in all lists |
| Front (of a list) | Its first remaining node: the head |
| Heap / min-heap | A tree-shaped structure that keeps the smallest element on top |
PriorityQueue |
Java's heap: add, poll (remove smallest), peek (look at smallest) |
peek() |
Look at the smallest without removing it: O(1) |
add() / poll() |
Insert / remove the smallest: O(log size) |
| Comparator | A function telling the heap which of two elements comes first |
Integer.compare(a, b) |
Compares two ints without overflow |
| Dummy node | A fake first node so the first real node needs no special case |
| Tail | The last node of the list being built |
| Divide and conquer | Split the problem in halves, solve each, combine (here: merge lists in pairs) |
| O(N log k) | N operations, each costing log k |
heapq |
Python's min-heap functions on a list |
priority_queue |
C++'s heap (a max-heap by default) |
| Integer overflow | A result too big for int wraps to a wrong value |
| Time Limit Exceeded (TLE) | Too slow for the judge's limit (8 s in the SyntaxPilot compiler) |
Summary
- The smallest remaining node is always at some list's front.
- Scanning every front for every pick is O(N·k): 20,000 lists time out.
- A min-heap of fronts gives the smallest in O(log k): poll, attach, push
min.next. O(N log k) time, O(k) space. - Skip
nulllists, useInteger.compare, returndummy.next. - Divide and conquer (merge in pairs) is also O(N log k); merging one by one is O(N·k).
Next episode: Reverse nodes in k-group.