Merge K Sorted Lists Problem


Description

LeetCode Problem 23. You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-list into one sorted linked-list and return it.

Example:

1
2
3
4
5
6
7
8
9
10
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6


Solution

This problem is similar to the merge two sorted lists problem.

We can compare the k heads of every linked list and get the node with the smallest value. We repeat this step until all lists are merged. The time complexity of this approach is O(kN), where N is the total number of nodes in all lists and k is the number of lists. This is because for every node in the merged list, it takes O(k) for comparison.

We can optimize this approach with a priority queue. We can insert all nodes into a priority queue. Then we create a new linked list by popping a node from the priority queue one at a time. As the priority queue will sort the nodes inserted into the queue, the final list popped will also be sorted.

The time complexity of this optimized approach is O(Nlogk). This is because the comparison cost will be reduced to O(logk) for every pop and insertion to priority queue.


Sample C++ Code

This is a C++ implementation of the priority queue approach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for (auto x : lists) {
        while (x != NULL) {
            pq.push(x->val);
            x = x->next;
        }
    }
    
    ListNode *temp = new ListNode();
    ListNode *head = temp;
    while (!pq.empty()) {
        temp->next = new ListNode(pq.top());
        pq.pop();
        temp = temp->next;
    }
    return head->next;
}

int main() {
    vector<ListNode*> lists;

    ListNode* l1 = new ListNode(1);
    l1->next = new ListNode(4);
    l1->next->next = new ListNode(5);

    ListNode* l2 = new ListNode(1);
    l2->next = new ListNode(3);
    l2->next->next = new ListNode(4);

    ListNode* l3 = new ListNode(2);
    l3->next = new ListNode(6);

    lists.push_back(l1);
    lists.push_back(l2);
    lists.push_back(l3);

    ListNode* head = mergeKLists(lists);
    while (head != nullptr) {
        cout << head->val << " ";
        head = head->next;
    }
    return 0;
}




Related Posts

Intersection Of Two Linked Lists Problem

LeetCode 160. Given the heads of two singly linked-lists headA...

Sort List Problem

LeetCode 148. Given the head of a linked list, return...

Reorder List Problem

LeetCode 143. You are given the head of a singly...

Linked List Cycle Problem

LeetCode 141. Given head, the head of a linked list,...

Linked List Cycle II Problem

LeetCode 142. Given the head of a linked list, return...

Insertion Sort List Problem

LeetCode 147. Given the head of a singly linked list,...