Problem overview
The method mergeKLists receives an array lists of k singly linked lists. Each list is sorted in ascending order. It must return one linked list holding all their nodes' values in ascending order. The array may be empty, and any of the lists may be empty.
The examples are written as arrays, but the real inputs are chains of ListNode objects, each with a val and a next. For lists = [[1, 4, 5], [1, 3, 4], [2, 6]] the answer is the list 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6. For [] and for [[]] the answer is an empty list, which is null.
The statement asks for O(n log k) time and O(k) extra space, where n is the total number of nodes.
Approach: always take the smallest head
At any moment, the next value in the merged list must be the smallest of the current heads of the lists, because each list is sorted and its head is its smallest remaining value. Taking that value, then moving that one list forward by a node, repeats until every list is used up.
The slow way scans all k heads each time to find the smallest, which costs O(k) per output node and O(n * k) overall. A min-heap does better. It is a collection that always gives back its smallest item, and both inserting and removing the smallest cost O(log size). Here the heap holds at most one node per list, so its size is never more than k, and each operation costs O(log k).
The loop is therefore: put the head of every non-empty list into the heap. Then, while the heap isn't empty, remove the smallest node, append its value to the result, and insert that node's successor if it has one. Each of the n nodes enters and leaves the heap once, so the total is O(n log k).
On the example, the heap starts with the three heads, 1, 1 and 2. One of the two 1s comes out first, and the next node of its list goes in. The other 1 follows, then 2, and each removal is followed by an insertion from the same list, until every list is used up. The output order is 1, 1, 2, 3, 4, 4, 5, 6.
Step by step
- Create the heap. The lesson uses a
MinHeapfrom thealgorithmspackage, stored inminNodes. A heap needs to know how to order its items, and it can't compareListNodeobjects by itself. So the constructor takes a comparator,(a, b) => a.val - b.val. A negative result meansacomes out first. - Visit every head with
for (const head of lists). - Insert only real nodes. An empty list is
null, which is falsy, soif (head)skips it. - Create a sentinel node,
dummy. The merged list is built after it, and the answer isdummy.next. The sentinel saves a special case for the first node. - Keep a walker,
tail, that points at the last node appended. - Loop while the heap has items. The package's heap reports its size in the property
n, so the condition isminNodes.n > 0. - Remove the smallest with
extract()intominNode. - Append a copy. Make a new node with
minNode.valand attach it astail.next. - Feed the heap from the same list. If
minNode.nextexists, insert it. That puts the list's next value into the competition. - Advance the walker with
tail = tail.next. - Return
dummy.next, the head of the merged list.
The solution in JavaScript
var algorithms = require('algorithms')
class Solution {
mergeKLists(lists) {
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 JavaScript details worth a look:
- JavaScript has no built-in heap. There is no priority queue in the language itself, so the lesson loads a library with
require. The calls you rely on are the constructor with a comparator,insert,extract, and the size propertyn. - The comparator contract. A comparison function returns a negative number, zero or a positive number. Subtracting the values is safe here because they are small integers.
ListNode. The starter code describes it as a constructor function takingvalandnext. With no arguments,valis 0 andnextisnull, sonew ListNode()makes a harmless sentinel.- Truthiness of
null.if (head)andif (minNode.next)are false fornull, which is how a missing node is represented. Node values of 0 are not an issue because the test is on the node, not its value. - Copying versus relinking. The code builds new nodes with
new ListNode(minNode.val)instead of reusing the old ones, so the input lists are left unchanged. Relinking the original nodes would save the allocation but would modify the inputs.
Complexity
Time: O(n log k). Each of the n nodes is inserted once and extracted once, and each operation costs O(log k) because the heap never holds more than k nodes. Seeding the heap adds at most k inserts, which is no more than n.
Space: O(k) extra for the heap, apart from the output list of n new nodes that the problem asks for. The input lists aren't copied.
Edge cases and common mistakes
lists = []. Nothing is inserted, the loop never runs, anddummy.nextisnull.- Lists that are all empty.
[[]]has a singlenullhead. The truthiness check skips it, and the result is againnull. - Some empty lists. Inserting a
nullinto the heap would crash the comparator ona.val, which is why the check comes first. - Duplicates. Equal values are fine. The comparator returns 0 for them, and both end up in the output.
- Forgetting to push the successor. The output would contain only the heads.
- Returning
dummy. That includes the sentinel with value 0 at the front. - Negative values. They work, because the comparator just subtracts.
Testing
[[1, 4, 5], [1, 3, 4], [2, 6]]gives1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6.[]gives an empty list.[[]]gives an empty list.[[], [-2, -1], [0]]gives-2 -> -1 -> 0.