Leetcode | Merge k Sorted Lists

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

想法很简单，就是两两合并。在Merge Two Sorted Lists这道题已经实现了两两合并的代码了，就直接拿过来用。

假设每条链平均长度为n，如果用二分法的话，也就是将所有的链分成两份，每份各自合并完之后再合并起来。递归的空间复杂度会是O(logk)，时间复杂度T(k)=2T(k/2) +O(nk)，由主定理得O(nklgk)。

主定理见wiki。

下面是两两合并的代码，时间复杂度是$O(2n+3n+ldots+kn)=O(k^2n)$.

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *mergeKLists(vector<ListNode *> &lists) {
12         if (lists.empty()) return NULL;
13         ListNode* head = lists[0];
14         for (int i = 1; i < lists.size(); ++i) {
15             head = mergeTwoLists(head, lists[i]);
16         }
17         
18         return head;
19     }
20     
21     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
22         ListNode *head, *t3;
23         head = t3 = new ListNode(0);
24         while (l1 != NULL && l2 != NULL) {
25             if (l1->val <= l2->val) {
26                 t3->next = l1;
27                 l1 = l1->next;
28             } else {
29                 t3->next = l2;
30                 l2 = l2->next;
31             }
32             t3 = t3->next;
33         }
34         
35         while (l1 != NULL) {
36             t3->next = l1;
37             t3= t3->next;
38             l1 = l1->next;
39         }
40         while (l2 != NULL) {
41             t3->next = l2;
42             t3 = t3->next;
43             l2 = l2->next;
44         }
45         
46         ListNode *ret = head->next;
47         delete head;
48         return ret;
49     }
50 };

下面是二分的实现。

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
12         ListNode h(0), *p = &h;
13         while (l1 || l2) {
14             if (l1 == NULL || (l2 != NULL && l2->val < l1->val)) {
15                 p->next = l2;
16                 l2 = l2->next;
17             } else {
18                 p->next = l1;
19                 l1 = l1->next;
20             }
21             p = p->next;
22         }
23         return h.next;
24     }
25     ListNode *mergeKLists(vector<ListNode *> &lists) {
26             if (lists.empty()) return NULL;
27             
28             vector<vector<ListNode *> > layers(2);
29             int cur = 0, next = 1;
30             layers[cur] = lists;
31             while (layers[cur].size() > 1) {
32                 layers[next].clear();
33                 for (int i = 0; i < layers[cur].size(); i += 2) {
34                     if (i + 1 < layers[cur].size()) layers[next].push_back(mergeTwoLists(layers[cur][i], layers[cur][i + 1]));
35                     else layers[next].push_back(layers[cur].back());
36                 }
37                 cur = !cur; next = !next;
38             }
39             return layers[cur][0];
40     }
41 };

非递归的空间复杂度可以优化到O(k)。