You are given an array of k linked lists, each sorted in non-decreasing order. Merge them into one sorted linked list and return its head.
Each list is shown in array notation for readability — [[1, 4, 5], [1, 3, 4], [2, 6]] is three sorted lists, and the answer is the single merged list [1, 1, 2, 3, 4, 4, 5, 6]. The outer array may be empty, and individual lists may be empty.
Example
Merging the three sorted lists interleaves their values into one sorted run.
Constraints
- k == lists.length
- 0 <= k <= 10^4
- 0 <= lists[i].length, and the total number of nodes across all lists is in the range [0, 10^4].
- -10^4 <= lists[i][j] <= 10^4
- Each lists[i] is sorted in non-decreasing order.
Intuition
The simplest correct approach ignores that the lists are sorted at all: pour every node into one array, sort it, and rebuild a single list from the sorted values.
function mergeKLists(lists) {
const values = [];
// Walk every list and dump all values into one array.
for (const head of lists) {
let node = head;
while (node) { values.push(node.val); node = node.next; }
}
values.sort((a, b) => a - b); // a full sort over all N values
// Rebuild a single sorted list.
const dummy = new ListNode(0);
let tail = dummy;
for (const v of values) { tail.next = new ListNode(v); tail = tail.next; }
return dummy.next;
}This is O(N log N) over all N nodes, and it throws away the fact that each list is already sorted — we re-sort values that arrived in order. Can we do better?
The key observation: at every step the next node of the answer is the smallest among the current heads of the k lists. Finding the minimum of k things, repeatedly, while one of them gets replaced each time, is exactly what a min-heap does in O(log k). Seed a heap with the head of each list; pop the global minimum, append it to the answer, and push that node's successor. Each of the N nodes is pushed and popped once, at O(log k) each.
Bridge to the stored solution: the Optimization code below reaches the same O(N log k) bound by a divide-and-conquer route instead — it pairs the lists up and merges them in log k rounds (the classic two-pointer merge of two lists), which avoids implementing a heap. The heap is the canonical Heaps-chapter framing; the pairwise merge is an equivalent, heap-free way to get the same complexity. The walkthrough below traces the heap model.
Walking the heap through [[1,4,5], [1,3,4], [2,6]]:
each list keeps one frontier head; the heap holds those heads — pop the min, advance that list
Seed the heap with each list's head: 1 (a), 1 (b), 2 (c). The min is the 1 from list a — pop it.
List a advances to 4, which joins the heap. The new min is the 1 from list b — pop it. Result: 1, 1.
List b advances to 3. The heap is now {4, 3, 2}; the min is 2 from list c — pop it. Result: 1, 1, 2.
List c advances to 6. The heap {4, 3, 6} has min 3 from list b — pop it. Result: 1, 1, 2, 3.
Keep popping the min and advancing its list: 4 (b), 4 (a), 5 (a), 6 (c). All lists drained — final: 1, 1, 2, 3, 4, 4, 5, 6.
Optimization
Divide and conquer (pairwise merge)
Merging two sorted lists is the classic two-pointer splice. Naively folding all k lists into an accumulator is O(kN); instead pair them up and merge in rounds, halving the list count each round. After log k rounds one list remains.
O(N log k) time for N total nodes, O(1) extra space beyond the output nodes (reusing input nodes).
function mergeKLists(lists) {
const mergeTwo = (a, b) => {
const dummy = new ListNode(0);
let tail = dummy;
while (a && b) {
if (a.val <= b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = a || b;
return dummy.next;
};
if (lists.length === 0) return null;
let merged = [...lists];
while (merged.length > 1) {
const next = [];
for (let i = 0; i < merged.length; i += 2) {
next.push(mergeTwo(merged[i], i + 1 < merged.length ? merged[i + 1] : null));
}
merged = next;
}
return merged[0];
}Complexity analysis
Time complexity: O(N log k) for N total nodes across k lists. Here's why:
- The heap holds at most
knodes (one per list), so each push and pop is O(log k). - Every one of the
Nnodes is pushed once and popped once.
So the merge does N × O(log k) work — overall O(N log k), versus O(N log N) for collecting and re-sorting everything. (The stored divide-and-conquer solution reaches the same bound: log k rounds, each touching every node once.)
Space complexity: O(k). Here's why:
- The heap never holds more than
knodes at a time — one frontier node per list.
The output list reuses the input nodes rather than allocating new ones, so beyond the heap the extra space is O(k) (not counting the output).
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| lists = [] | []null | No lists at all — the heap is never seeded, result is empty. |
| lists = | []null | A single empty list — nothing to merge, return empty. |
| lists = 789 | [7,8,9]789null | One non-empty list passes straight through, already sorted. |
| lists = [[2],[],[1,3]] | [1,2,3]123null | An empty list mixed in is skipped; the rest interleave. |
| lists = 44 44 | [4,4,4,4]4444null | All-equal values across lists — duplicates are kept, order stable. |
| lists = -21 -13 | [-2,-1,1,3]-2-113null | Negatives interleave correctly: -2, -1, 1, 3. |
Try it yourself
Write your solution against the real judge before checking the reference.