How to Merge k Sorted Lists using Recursive Divide and Conquer A

  • Time：2020-09-12 10:17:13
  • Class：Weblog
  • Read：41

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6

There are many algorithms that we can use to merge K sorted lists however the performance complexity varies.

Bruteforce Algorithm to Merge K sorted lists

Despite the lists are all sorted, we can first add all lists into an array, then sort the array, then finally convert it back to linked list.

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        vector<int> data;
        // push nodes to vector
        for (auto &n: lists) {
            while (n) {
                data.push_back(n->val);
                n = n->next;
            }
        }
        sort(begin(data), end(data));
        // convert vector back to linked list
        ListNode *dummy = new ListNode(-1);
        ListNode *p = dummy;
        for (const auto &n: data) {
            ListNode *cur = new ListNode(n);
            p->next = cur;
            p = p->next;
        }
        return dummy->next;
    }
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        vector<int> data;
        // push nodes to vector
        for (auto &n: lists) {
            while (n) {
                data.push_back(n->val);
                n = n->next;
            }
        }
        sort(begin(data), end(data));
        // convert vector back to linked list
        ListNode *dummy = new ListNode(-1);
        ListNode *p = dummy;
        for (const auto &n: data) {
            ListNode *cur = new ListNode(n);
            p->next = cur;
            p = p->next;
        }
        return dummy->next;
    }
};

The space requirement is O(N), and the time complexity is O(N.LogN) where N is the number of nodes in K sorted list. Apparently this is not optimal. If we assume the average length of each sorted list is N and there are K lists, thus, the space requirement is O(KN) and the time complexity is O(KN.LogN).

Bruteforce Algorithm to Merge K sorted lists using Priority Queue

Instead of sorting, we can push the nodes into a priority queue, then pop out in the expected order. We need to use the std::greater to reverse the default popping sequence of a priority queue.

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        // inverse the order of priority queue from smallest to largest sequence
        priority_queue<int, vector<int>, std::greater<int>> data;
        for (auto &n: lists) {
            while (n) {
                data.push(n->val);
                n = n->next;
            }
        }
        ListNode *dummy = new ListNode(-1);
        ListNode *p = dummy;
        while (!data.empty()) {
            auto n = data.top();
            data.pop();
            ListNode *cur = new ListNode(n);
            p->next = cur;
            p = p->next;
        }
        return dummy->next;
    }
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        // inverse the order of priority queue from smallest to largest sequence
        priority_queue<int, vector<int>, std::greater<int>> data;
        for (auto &n: lists) {
            while (n) {
                data.push(n->val);
                n = n->next;
            }
        }
        ListNode *dummy = new ListNode(-1);
        ListNode *p = dummy;
        while (!data.empty()) {
            auto n = data.top();
            data.pop();
            ListNode *cur = new ListNode(n);
            p->next = cur;
            p = p->next;
        }
        return dummy->next;
    }
};

The space complexity is O(KN) and the time complexity is also O(KN.LogN) as it takes O(LogN) to insert/pop for a priority queue.

Merge Sorted Lists One By One

First, we can easily merge two linked lists by comparing the two pointers, link and move the smaller one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

ListNode* merge(ListNode *a, ListNode *b) {
    ListNode* dummy = new ListNode(-1);
    ListNode* head = dummy;
    while (a && b) {    
        if (a->val < b->val) {
            head->next = a;
            a = a->next;
        } else {
            head->next = b;
            b = b->next;
        }
        head = head->next;
    }
    if (a) head->next = a;
    if (b) head->next = b;
    return dummy->next;
}
ListNode* merge(ListNode *a, ListNode *b) {
    ListNode* dummy = new ListNode(-1);
    ListNode* head = dummy;
    while (a && b) {    
        if (a->val < b->val) {
            head->next = a;
            a = a->next;
        } else {
            head->next = b;
            b = b->next;
        }
        head = head->next;
    }
    if (a) head->next = a;
    if (b) head->next = b;
    return dummy->next;
}

Then, we can start merging one by one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        ListNode* a = lists[0];
        for (int i = 1; i < lists.size(); ++ i) {
            a = merge(lists[i], a);
        }
        return a;
    }
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        ListNode* a = lists[0];
        for (int i = 1; i < lists.size(); ++ i) {
            a = merge(lists[i], a);
        }
        return a;
    }
};

The complexity of merging two linked lists is O(M+N) where M and N are the length of two sorted linked lists respectively. Then, the overall complexity in this case is O(KN). Merging first two pairs require O(2N), then the list becomes length 2N, the merge 2N and N requires O(3N) etc. That sums to: 2N+3N+4N+…KN=O(KN)

Merge Sorted Lists using Divide-and-Conquer Strategy

Merging K Lists can be done in O(LogK) time. We can divide the lists into two parts, and recursively merge two into one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        if (n == 0) return nullptr;
        if (n == 1) return lists[0];
        int m = n / 2;
        vector<ListNode*> a(begin(lists), begin(lists) + m);
        vector<ListNode*> b(begin(lists) + m, end(lists));
        return merge(mergeKLists(a), mergeKLists(b));
    }
}
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        if (n == 0) return nullptr;
        if (n == 1) return lists[0];
        int m = n / 2;
        vector<ListNode*> a(begin(lists), begin(lists) + m);
        vector<ListNode*> b(begin(lists) + m, end(lists));
        return merge(mergeKLists(a), mergeKLists(b));
    }
}

The ideal time complexity is O(NLogK) and the space requirement is O(LogK) due to stacks required by recursion. However, there is overhead of creating copies of two parts of the lists, hence, this may not be efficient in terms of memory and performance.

–EOF (The Ultimate Computing & Technology Blog) —

Recommend：
The Best Instagram Feed WordPress Plugins to Use
Trie Class Data Structure in Python
How to Monitor the CPU Temperature of Raspberry PI using Python
Listen to what an SEO expert has to say about its benefits
Depth First Search Algorithm to Compute the Smallest String Star
Algorithm to Check if All Points are On the Same Line
Prefix Sum Algorithm to Count Number of Nice Subarrays
How to Append Another List to a Existing List in Python? (Differ
Linear Algorithm to Check If All 1’s Are at Least Length K
Finding the Root of a Tree (Finding the Common Destination)
Share：Facebook Twitter
Comment list
Comment add