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

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

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

推荐阅读：
无公害蔬菜如何用感官简单进行识别　 食品安全危机期，谁来保障吃的安全？　 夏季熬制“开花”绿豆汤防暑又解毒　 炎炎夏日如何制作生津止渴的酸梅汤　 细数一根香蕉的12大神奇养生功效　 职场男性食补方略及饮食注意事项　 三款肉制食品诱惑红超标北京已下架　 保健食品虚假广告花样百出太坑人　 冰淇淋为何要加如此多的食品添加剂　 肉禽类的这些部位千万不要去吃　
评论列表
添加评论