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

  • 时间：2020-09-12 10:17:13
  • 分类：网络文摘
  • 阅读：146 次

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

推荐阅读：
数学题：三角形ABC的面积是36平方厘米　 数学题：小明乘车从家到郊区看望外婆　 数学题：甲、乙各存款若干元　 倒推法练习题　 数学题：一群猴子吃桃子　 数学题：甲、乙、丙、丁四人共植树60棵　 数学题：货车15小时走完全程　 数学题：玉龙粮食加工厂生产一批面粉　 数学题：从甲地到乙地的公路，只有上坡路和下坡路　 数学题：求MN的长是多少　
评论列表
添加评论