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

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

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

推荐阅读：
家乡的上灯节作文　 欢乐的火把节_描写少数民族节日的小学生作文800字　 欢欢喜喜闹元宵_关于描写元宵佳节的小学生作文350字　 元旦节的作文300字　 令人难忘的中秋节作文　 古埃及分数　 长方体和正方体思维导图　 一个整数除以小数是什么含义？　 平行四边形、梯形、三角形的高一定要画成虚线吗？　 格子乘法介绍　
评论列表
添加评论