Home
How to Merge k Sorted Lists using Recursive Divide and Conquer Algorithms?
Tags:, , , ,

How to Merge k Sorted Lists using Recursive Divide and Conquer Algorithms?

January 1, 2020 No Comments algorithms, c / c++, data structure, recursive

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.

Pushing Nodes directly to Priority Queue

We can push the list nodes directly to the priority queue – and thus saving time to recreating them when popping out. In order to make priority queue popping out the correct order, we have to provide a custom comparator and use the keyword decltype to provide it in the generic template constructor of the 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
33
34
35
36

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return NULL;
        auto cmp = [](ListNode *a, ListNode *b) {
            return a->val > b->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
        for (const auto &n: lists) {
            auto head = n;
            while (head != NULL) {
                pq.push(head);
                head = head->next;
            }
        }
        auto dummy = new ListNode(-1);
        auto head = dummy; 
        while (!pq.empty()) {
            head->next = pq.top();
            pq.pop();
            head = head->next;
        }
        head->next = NULL;
        return dummy->next;
    }
};
/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return NULL;
        auto cmp = [](ListNode *a, ListNode *b) {
            return a->val > b->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
        for (const auto &n: lists) {
            auto head = n;
            while (head != NULL) {
                pq.push(head);
                head = head->next;
            }
        }
        auto dummy = new ListNode(-1);
        auto head = dummy; 
        while (!pq.empty()) {
            head->next = pq.top();
            pq.pop();
            head = head->next;
        }
        head->next = NULL;
        return dummy->next;
    }
};

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) —

GD Star Rating
loading...
1091 words
Last Post: The String ZigZag Conversion Algorithms
Next Post: Using Recursive Merge Sort Algorithm to Sort a Linked List in O(NLogN)

The Permanent URL is: How to Merge k Sorted Lists using Recursive Divide and Conquer Algorithms?

Related posts:

  1. C++ Coding Exercise – Product of Array Except Self Given an array of n integers where n > 1, nums, return an array output...
  2. The Custom Sort String Algorithm with Count and Write S and T are strings composed of lowercase letters. In S, no letter occurs more...
  3. Binary Tree Algorithm: Checking Leaves in the Same Level Given a binary tree root, return whether all leaves are at the same level. Constraints...
  4. C++ Chess Board Printing in Windows Using CodePage 437 – Extended ASCII Well, most people, when they start programming in C/C++, they would like to print something...
  5. The String ZigZag Conversion Algorithms The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows...
  6. Review: Lenovo ThinkCenter M900 Tower Station The new machine Lenovo ThinkCenter M900 Tower Station has just arrived! my current Lenovo Laptop...
  7. Breadth First Search Algorithm to Find Nearest Right Node in Binary Tree Given the root of a binary tree and a node u in the tree, return...
  8. Get Help With SQL Database Design and Development For Your Business with SQL Server Consulting If you want to design an SQL database from scratch, revamp an existing system, or...

Leave a Reply