Problem
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
Solution 1: Brute Force
Time complexity: O(nk)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua, 420 ms class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode dummy(0); ListNode *cur = &dummy; while (true) { ListNode** min_head = nullptr; for (auto& head : lists) { if (!head) continue; if (!min_head || head->val < (*min_head)->val) min_head = &head; } if (!min_head) break; cur->next = new ListNode((*min_head)->val); cur = cur->next; *min_head = (*min_head)->next; } return dummy.next; } }; |
Solution 2: Heap / Priority Queue
Time complexity: O(nlogk)
Space complexity: O(k)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua, 16 ms (<99.88%) class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode dummy(0); ListNode *cur = &dummy; auto comp = [](ListNode* a, ListNode* b) { return a->val > b->val; }; priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> q(comp); for (ListNode* list : lists) if (list) q.push(list); while (!q.empty()) { cur->next = q.top(); q.pop(); cur = cur->next; if (cur->next) q.push(cur->next); } return dummy.next; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment