Problem overview
MergeKLists(lists) receives an array of k linked lists, each sorted in ascending order, and must return one sorted linked list containing all their values. Some lists can be empty (null), and the array itself can be empty.
In the first example, [[1,4,5],[1,3,4],[2,6]] merges into [1,1,2,3,4,4,5,6]. An empty array and an array holding one empty list both give an empty list, that is, null.
The note sets the budget: O(n log k) time and O(k) extra space, where n is the total number of nodes and k is the number of lists.
Approach: always take the smallest head
Merging two sorted lists is easy: compare the two heads, take the smaller one, repeat. With k lists the same idea works. The next value of the merged list is always the smallest of the k current heads, because each list is sorted and nothing in a list can be smaller than its head.
The simple version scans all k heads every time, which costs O(k) per output node and O(n · k) overall. The improvement is to keep the current heads in a min-heap, a structure that gives you the smallest item in O(log k) and accepts a new item in O(log k). The heap never holds more than one node per list, so it has at most k items.
The loop is then:
- Put the head of every non-empty list into the heap.
- Take the smallest node out and append its value to the result.
- If that node has a successor, put the successor into the heap.
- Repeat until the heap is empty.
Each of the n output nodes costs one removal and at most one insertion, each O(log k), which gives O(n log k).
Step by step
- Create the heap. C# provides
PriorityQueue<TElement, TPriority>. It stores each element together with a separate priority, so usePriorityQueue<ListNode, int>with the node as the element and its value as the priority. The default ordering ofintdequeues the lowest priority first, which makes it a min-heap. - Visit every list head with
foreach. - Enqueue the non-null heads as
Enqueue(head, head.val). Empty lists are skipped. - Create a dummy node. The merged list is built as
dummy.next, so the first real node needs no special case. - Keep a
tailwalker starting at the dummy. It always points to the last appended node. - Loop while
minNodes.Count > 0. Each iteration produces one output node. - Dequeue the node with the smallest value into
minNode. - Append a new node with
minNode.valtotail.next. - Feed the heap from the same list. If
minNode.nextexists, enqueue it, with its own value as the priority. A list therefore always has exactly one node waiting in the heap until it runs out. - Advance
tailto the node just appended. - Return
dummy.next, the head of the merged list.
The solution in C#
class Solution {
public ListNode MergeKLists(ListNode[] lists) {
PriorityQueue<ListNode, int> minNodes = new PriorityQueue<ListNode, int>();
foreach (ListNode head in lists) {
if (head != null) {
minNodes.Enqueue(head, head.val);
}
}
ListNode dummy = new ListNode();
ListNode tail = dummy;
while (minNodes.Count > 0) {
ListNode minNode = minNodes.Dequeue();
tail.next = new ListNode(minNode.val);
if (minNode.next != null) {
minNodes.Enqueue(minNode.next, minNode.next.val);
}
tail = tail.next;
}
return dummy.next;
}
}
Some C# details are worth a closer look:
- Element and priority are separate. Unlike some heap types,
PriorityQueuedoesn't compare the elements themselves.ListNodeneeds no comparison code, because the priority carries the ordering.Enqueue(element, priority)takes both. - The type needs
System.Collections.Generic.PriorityQueueis in that namespace, likeListandDictionary, and has been part of .NET since version 6. Countis a property. No parentheses, and the loop condition isminNodes.Count > 0.- Dequeue on an empty queue throws.
Dequeue()raises anInvalidOperationExceptionwhen nothing is left. The loop condition makes sure it is only called on a non-empty queue. - Ties come out in no promised order. Two nodes with the same priority can leave in either order. That is fine here, because equal values are interchangeable in the output.
- The result has new nodes. The solution builds new
ListNodeobjects from the values rather than relinking the inputs, so the input lists stay unchanged.
A short trace
For [[1,4,5],[1,3,4],[2,6]] the heap starts with the nodes 1, 1 and 2. The first removal gives a 1 from one of the first two lists, and its successor (4 or 3) goes in. The next removal gives the other 1, then the 2, then 3, and so on. The heap holds at most three nodes at any moment, one per list, and it empties after the last 6 is taken and appended. The output is 1, 1, 2, 3, 4, 4, 5, 6.
Complexity
Time: O(n log k). Building the first heap takes at most k insertions, each O(log k). After that, each of the n nodes is dequeued once and its successor is enqueued at most once, each O(log k) because the heap holds at most k items.
Extra space: O(k). The heap holds at most one node per list. The merged list has n new nodes, but that is the output itself.
Edge cases and common mistakes
- No lists. An empty array skips the
foreach, the heap stays empty, and the method returnsdummy.next, which isnull. - Only empty lists.
[null]behaves the same way, because null heads are never enqueued. - Enqueuing a null head. Reading
head.valonnullthrows aNullReferenceException, so the check comes first. - Forgetting the successor. If you never enqueue
minNode.next, the output contains only the first node of each list. - Enqueuing the whole list. Putting all
nnodes into the heap works but needsO(n)space and loses the point of the exercise. - Duplicate values. The two 1s in the example are separate nodes with the same priority, and both end up in the output.
- Returning
dummy. The dummy holds the default value 0, which doesn't belong in the result.
Testing
[[1,4,5],[1,3,4],[2,6]]gives[1,1,2,3,4,4,5,6].[]gives[].[[]]gives[].[[-2,-1],[-3]]gives[-3,-2,-1], so negative values work too.