给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

**输入：**lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
**解释：**链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

**输入：**lists = []
输出：[]

示例 3：

**输入：**lists = [[]]
输出：[]

提示：

k == lists.length

0 <= k <= 10^4

0 <= lists[i].length <= 500

-10^4 <= lists[i][j] <= 10^4

lists[i] 按 升序 排列

lists[i].length 的总和不超过 10^4

使用最小堆

每个链表头节点入堆，每次取出堆顶，如果堆顶节点有后续节点则后续节点继续入堆

可以使用一个虚拟头节点来避免堆为空的讨论

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
class Solution {
public:
    struct Status {
        ListNode *node;
        bool operator<(const Status &r) const {
            return node->val > r.node->val;
        }
    };
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<Status> pq;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i] != nullptr)
                pq.push({lists[i]});
        }
        ListNode head;
        ListNode *pre = &head;
        while (!pq.empty()) {
            Status cur = pq.top();
            pq.pop();
            pre->next = cur.node;
            pre = pre->next;
            if (cur.node->next != nullptr)
                pq.push({cur.node->next});
        }
        return head.next;
    }
};