首页 > 代码库 > Leetcode | Merge k Sorted Lists

Leetcode | Merge k Sorted Lists

2024-07-02 15:24:21   226人阅读

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

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

假设l[i]是第i条链的长度，那么共有k-1次合并，最坏情况下每次合并的时间复杂度为O(l[i - 1] + l[i])，0 < i < k，因此最坏情况下总的复杂度为O(l[0]+2*l[1]+...+2*l[k - 2] +l[k-1])。如果链的最大长度为n，那么算法复杂度就是O(2*n*(k-1))=O(nk)。

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

主定理见wiki。

 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 };

 


联系
我们