Problem overview
The method mergeKLists receives an array of k linked lists, each sorted in ascending order. Some of the entries can be null, which is an empty list. It must return one sorted linked list holding every value from all of them. The statement sets a budget of O(n log k) time and O(k) extra space, where n is the total number of nodes.
In the first example, the lists are 1 -> 4 -> 5, 1 -> 3 -> 4 and 2 -> 6. The merged list is 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6. If the array is empty, or holds only empty lists, the answer is null, an empty list.
Approach: always take the smallest head
Each list is already sorted, so the smallest value left anywhere is always the head of one of the lists. The merged list is built by repeating one move: take the smallest of the k heads, append it to the result, and move that list forward by one node.
The simple way to find the smallest head is to scan all k heads each time. That costs O(k) per output node, O(n * k) in total. A min-heap does the same job faster. A heap is a structure that keeps its smallest element ready to extract, and both inserting an element and extracting the smallest take O(log k) time.
The heap holds the current head of every list that still has nodes, so it never contains more than k nodes. Each step extracts the smallest node. If that node has a successor, the successor becomes its list's new head and goes into the heap. When the heap is empty, every list has been consumed.
Every output node costs one extract and at most one insert, each O(log k), so the total is O(n log k).
Watch the first example. The heap starts with the three heads: 1, 1 and 2. Extract a 1, append it, and insert its successor 4, so the heap holds 1, 2 and 4. Extract the other 1 and insert 3, giving 2, 3 and 4. Extract 2, insert 6, and so on until the heap runs dry.
Step by step
- Create a
MinHeapnamedminNodesfrom the lesson's heap library. It can't compareListNodeobjects on its own, so pass it a comparator,(a, b) => a.val - b.val. A negative result meansacomes first, a positive one meansbdoes. - Loop over the array with
for (const head of lists). - Insert each head that is truthy. A
nullentry is an empty list and has nothing to offer, so it is skipped. - Create a sentinel,
const dummy = new ListNode(). The result will bedummy.next. The sentinel means the first appended node needs no special case. - Declare a walker
tailthat starts atdummyand always points at the last node appended. - Loop while the heap is not empty: the heap reports its size as
minNodes.n. - Extract the smallest node into
minNode. - Append a new node with
minNode.valtotail.next. The result is made of new nodes, so the input lists are not relinked. - Feed the heap: if
minNodehas anext, insert it. Each list gives the heap one node at a time. - Advance
tailonto the node just appended. - Return
dummy.next, the head of the merged list. The dummy itself isn't part of the answer.
The solution in TypeScript
class Solution {
mergeKLists(lists: (ListNode | null)[]): ListNode | null {
const minNodes = new algorithms.DataStructures.Heap.MinHeap((a, b) => a.val - b.val);
for (const head of lists) {
if (head) {
minNodes.insert(head);
}
}
const dummy = new ListNode();
let tail = dummy;
while (minNodes.n > 0) {
const minNode = minNodes.extract();
tail.next = new ListNode(minNode.val);
if (minNode.next) {
minNodes.insert(minNode.next);
}
tail = tail.next;
}
return dummy.next;
}
}
The TypeScript details worth knowing:
- The heap comes from the lesson. JavaScript and TypeScript have no built-in priority queue, so the lesson provides a ready-made
MinHeap. Its methods here areinsert,extractand the size propertyn. In another project you would write a heap yourself or use a library. - The comparator. A comparison function returns a number: negative, zero or positive. Subtracting values is a short way to get that, and it is safe here because values stay between -10,000 and 10,000. The same convention is used by
Array.prototype.sort, which, with no comparator, would sort numbers as strings and put 10 before 9. - The array type.
(ListNode | null)[]is an array whose items are nodes ornull. The parentheses matter:ListNode | null[]would mean something else, a node or an array ofnull. - Truthiness check.
if (head)is false fornull, so empty lists are skipped.for...ofwalks the array's items, not its indices. - Why
tailis advanced last. Aftertail.next = new ListNode(...), the assignmenttail = tail.nextmoves the walker to the node just created.
Complexity
Let n be the total number of nodes and k the number of lists.
Time: O(n log k). Building the heap takes at most k inserts, O(k log k). After that, each of the n nodes is extracted once and its successor inserted at most once. The heap never holds more than k nodes, so each operation takes O(log k).
Space: O(k) extra. The heap holds at most one node per list. The merged list has n new nodes, but that is the output.
Edge cases and common mistakes
- An empty array. Nothing is inserted, the loop doesn't run, and
dummy.nextisnull. - Only empty lists.
[null]works the same way: the truthiness check skips it. - Forgetting to filter
null. Insertingnullmakes the comparator read.valofnull, which throws aTypeError. - Equal values. Two lists starting with 1 are both in the heap and both come out. Which of the two equal nodes comes first doesn't matter, because the values are the same.
- Not feeding the heap. If the successor isn't inserted after each extract, only the heads of the lists end up in the result.
- Returning
dummy. That includes the sentinel, so the result begins with a stray extra node. - Lists of different lengths. One long list among short ones works naturally: when the others are exhausted, the heap holds only that list's current node, and the loop keeps taking it.
- Mixing up the approach with pairwise merging. Merging the lists one after another also works, but re-walks the growing result and can cost more than
O(n log k).
Testing
[[1, 4, 5], [1, 3, 4], [2, 6]]gives[1, 1, 2, 3, 4, 4, 5, 6].[]gives an empty list.[[]]gives an empty list.[[5], [], [1, 2]]gives[1, 2, 5].