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: Min heap
Time complexity: O(nklogk)
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 class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode dummy(0); ListNode *tail = &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()) { tail->next = q.top(); q.pop(); tail = tail->next; if (tail->next) q.push(tail->next); } return dummy.next; } }; |
Solution 2: Merge Sort
Time complexity: O(nklogk)
Space complexity: O(logk)
C++
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 |
// Author: Huahua class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { return merge(lists, 0, lists.size() - 1); } private: ListNode* merge(vector<ListNode*>& lists, int l, int r) { if (l > r) return nullptr; if (l == r) return lists[l]; if (l + 1 == r) return mergeTwoLists(lists[l], lists[r]); int m = l + (r - l) / 2; auto l1 = merge(lists, l, m); auto l2 = merge(lists, m + 1, r); return mergeTwoLists(l1, l2); } ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail = &dummy; while (l1 && l2) { if (l1->val > l2->val) swap(l1, l2); tail->next = l1; l1 = l1->next; tail = tail->next; } if (l1) tail->next = l1; if (l2) tail->next = l2; return dummy.next; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment