LeetCode C++ 23. Merge k Sorted Lists【排序堆分治链表】困难

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6

Example 2:

Input: lists = [] Output: []

Example 3:

Input: lists = [[]] Output: []

Constraints:

k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i] is sorted in ascending order.The sum of lists[i].length won't exceed 10^4.

题意：给出一个大小为 k 的链表数组，每个链表都已经按照升序排列，将所有链表合并到一个升序链表中，返回合并后的链表。

---

解法1 堆排序

这道题是多路归并排序。我们可以使用一个大小为 k 的最小堆优先队列，将链表的头指针都放进去，然后出队当前优先队列中的最小值，挂上结果链表的尾部，再让出队的那个结点的下一个入队。接着再出队当前最小堆堆顶元素……直到优先队列为空。具体代码如下：

class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { int n = lists.size(); ListNode dummy(0), *rear = &dummy; auto cmp = [](ListNode *a, ListNode *b) { return a->val > b->val; }; priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp); for (int i = 0; i < n; ++i) if (lists[i]) pq.push(lists[i]); while (!pq.empty()) { ListNode *t = pq.top(); pq.pop(); rear->next = new ListNode(t->val); rear = rear->next; if (t->next) pq.push(t->next); } return dummy.next; } };

效率如下，时间复杂度为 $O(n\log k)$ ：

执行用时：60 ms, 在所有 C++ 提交中击败了37.43% 的用户 内存消耗：14.2 MB, 在所有 C++ 提交中击败了16.87% 的用户