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.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[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% 的用户