Problem Explanation

We are given k sorted linked lists and we need to merge all of them into a single sorted linked list.

Consider the following input:

1[
2  1->4->5,
3  1->3->4,
4  2->6
5]

Here, we see three linked lists. The first list is 1 -> 4 -> 5, second list is 1 -> 3 -> 4 and third list is 2 -> 6. We need to merge these lists in a sorted manner.

The result should be: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6.

Solution Approach

The solution uses a priority queue (min-heap) to keep track of the minimum node at any time. Priority queue is a data structure that provides constant time complexity for retrieval and removal of the minimum element. We start by adding the first node of each list into the priority queue. We then start a while loop where we keep extracting the node with the smallest value, add it to our final result, and push the next node of the extracted node into the queue, until the queue is empty.

Implementation

C++ Solution

1
2cpp
3class Solution {
4 public:
5  ListNode* mergeKLists(vector<ListNode*>& lists) {
6    ListNode dummy(0);
7    ListNode* curr = &dummy;
8
9    // Lambda function to compare two nodes
10    auto compare = [](ListNode* a, ListNode* b) { return a->val > b->val; };
11
12    // Priority queue
13    priority_queue<ListNode*, vector<ListNode*>, decltype(compare)> minHeap(compare);
14
15    // Add the first node of each list to the priority queue
16    for (ListNode* list : lists)
17      if (list != nullptr)
18        minHeap.push(list);
19
20    // While the queue is not empty
21    while (!minHeap.empty()) {
22      // Get the node with the smallest value
23      ListNode* minNode = minHeap.top();
24      minHeap.pop();
25
26      // If the smallest node has a next node, push it to the queue
27      if (minNode->next)
28        minHeap.push(minNode->next);
29
30      // Add the smallest node to the final list
31      curr->next = minNode;
32      curr = curr->next;
33    }
34
35    return dummy.next;
36  }
37};

Python Solution

1
2python
3import heapq
4class Solution:
5    def mergeKLists(self, lists):
6        dummy = curr = ListNode(0)
7        heap = []
8        
9        for i in range(len(lists)):
10            if lists[i]:
11                heapq.heappush(heap, (lists[i].val, i))
12                lists[i] = lists[i].next
13                
14        while heap:
15            val, idx = heapq.heappop(heap)
16            curr.next = ListNode(val)
17            curr = curr.next
18            
19            if lists[idx]:
20                heapq.heappush(heap, (lists[idx].val, idx))
21                lists[idx] = lists[idx].next
22                
23        return dummy.next

Both solutions use the same approach (using a heap to obtain the minimum value node in constant time). In the Python solution, we use the heapq library to get a priority queue. The ListNode object corresponds to the ListNode object in the linked lists. The differences in the syntax are only due to the differences between the C++ and Python languages.## JavaScript Solution

1
2javascript
3var mergeKLists = function(lists) {
4    var merge = function(l, r){
5        if(l == null) return r;
6        if(r == null) return l;
7        if(l.val < r.val){
8            l.next = merge(l.next, r);
9            return l;
10        }
11        else{
12            r.next = merge(l, r.next);
13            return r;
14        }
15    }
16
17    var sort = function(lists, start, end){
18        if(start === end) return lists[start];
19        else if(start < end){
20            var mid = Math.floor((end - start) / 2) + start;
21            var l = sort(lists, start, mid);
22            var r = sort(lists, mid + 1, end);
23            return merge(l, r);
24        }
25        else {
26            return null;
27        }
28    } 
29
30    if(lists == null || lists.length == 0) return [];
31
32    return sort(lists, 0, lists.length - 1);
33};

In JavaScript, we create two helper functions named merge and sort. The merge function is responsible for merging two linked lists, and the sort function divides the task into sub-problems using the divide and conquer technique, and uses the merge function to merge two lists at a time.

Java Solution

1
2java
3import java.util.PriorityQueue;
4
5public class Solution {
6    public ListNode mergeKLists(ListNode[] lists) {
7        if (lists == null || lists.length == 0) return null;
8        
9        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, (a, b) -> a.val - b.val);
10
11        for (ListNode node : lists)
12            if (node != null)
13                queue.add(node);
14
15        ListNode dummy = new ListNode(0);
16        ListNode tail = dummy;
17
18        while (!queue.isEmpty()) {
19            tail.next = queue.poll();
20            tail = tail.next;
21            
22            if (tail.next != null)
23                queue.add(tail.next);
24        }
25        
26        return dummy.next;
27    }
28}

In Java, we also utilize a priority queue (implemented as a heap in Java) to keep track of the smallest node. PriorityQueue with comparator (a, b) -> a.val - b.val ensures that the node with the smallest value is located at the head of the queue. The rest of the logic is similar to the other language solutions. We add the smallest node to the final list and enqueue the next node of it to the priority queue until the queue is empty.