Last active
June 23, 2022 11:36
-
-
Save lcpz/4c6213b507cd5ec3a953109ee2c9cf4f to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// https://leetcode.com/problems/merge-k-sorted-lists | |
/* | |
* O(N log k) time and O(1) space, where N is the total number of nodes. | |
* | |
* # Explanation of the time complexity | |
* | |
* Let n be an upper bound on the number of nodes of each list. | |
* | |
* We iteratively merge pairs of lists as follows: | |
* | |
* Iteration 1. Merge k/2 lists. Each merge requires O( n) + O( n) = O(2n) time. | |
* Iteration 2. Merge k/4 lists. Each merge requires O(2n) + O(2n) = O(4n) time. | |
* Iteration 3. Merge k/8 lists. Each merge requires O(4n) + O(4n) = O(8n) time. | |
* ... | |
* Iteration i. Merge k/2^i lists. Each merge requires O(2^i n) time. | |
* | |
* As we can merge at most \log_2 k times, the time complexity is: | |
* | |
* \sum_{i = 1}^{\log_2 k} (nk 2^i)/2^i = O(nk log_2 k). | |
* | |
* Finally, since O(nk) = O(N), then O(nk log_2 k) = O(N log_2 k) = O(N log k). | |
*/ | |
class Solution { | |
ListNode* mergeTwoLists(ListNode* a, ListNode* b) { | |
ListNode head, * tail = &head; | |
while (a && b) { | |
if (a->val <= b->val) { | |
tail->next = a; | |
a = a->next; | |
} else { | |
tail->next = b; | |
b = b->next; | |
} | |
tail = tail->next; | |
} | |
tail->next = a ? a : b; | |
return head.next; | |
} | |
public: | |
ListNode* mergeKLists(vector<ListNode*>& lists) { | |
if (lists.empty()) return nullptr; | |
int len = lists.size(), i; | |
while (len > 1) { | |
for (i = 0; i < len / 2; ++i) | |
lists[i] = mergeTwoLists(lists[i], lists[len - 1 - i]); | |
len = (len + 1) / 2; | |
} | |
return lists[0]; | |
} | |
// O(N log k) time and O(k) space, where N is the total number of nodes. | |
ListNode* mergeKListsHeap(vector<ListNode*>& lists) { | |
if (lists.empty()) return nullptr; | |
auto cmp = [](auto a, auto b) { return a->val > b->val; }; | |
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> q(cmp); | |
for (auto list : lists) if (list) q.push(list); // avoid pushing empty lists | |
ListNode head, *tail = &head, *node; | |
while (!q.empty()) { | |
node = q.top(); | |
q.pop(); | |
if (node->next) q.push(node->next); | |
tail->next = node; | |
tail = node; | |
} | |
return head.next; | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment