问题描述
LeetCode 23. 合并 K 个升序链表 (opens in a new tab)，难度困难。
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]按 升序 排列lists[i].length的总和不超过10^4
题解
优先队列（小顶堆）
解题思路：拿到题首先想到以下几个方法
- 暴力：将所有数据存入数组中再排序，最后转成链表；时间复杂度
O(NlogN)（N表示所有链表的节点总数），空间复杂度O(N)。 - 两两合并：两两合并链表，最终将所有链表合并为一个；每次合并的时间复杂度是
O(N)，总的时间复杂度是O(KN)。 - 优先队列（小顶堆）：使用小顶堆，每次将堆顶元素（当前最小节点）取出并放入结果链表中，然后将该节点的下一个节点放入堆中；时间复杂度
O(NlogK)，其中N是所有链表节点的总数，空间复杂度O(K)。
优先队列实现思路：创建优先队列（小顶堆）来处理 K 个链表的合并。每次获取当前所有链表中最小的节点。
- 我们需要使用优先队列存储每个链表的头节点。
- 每次从优先队列中取出最小的节点，将其加入到结果链表中。
- 如果取出的节点有下一个节点，则将下一个节点放入优先队列。
Solution.java
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// 定义小顶堆
PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
});
// 将 list 的表头都放进优先队列
for (ListNode head : lists) {
if (head != null) {
pq.offer(head);
}
}
ListNode result = new ListNode();
ListNode temp = result;
// 优先队列不为空的情况下
while (!pq.isEmpty()) {
// 从 pq 里面取出最小的节点 node 放入 temp 节点后面
ListNode node = pq.poll();
temp.next = node;
temp = temp.next;
// 将 node 节点的后续节点加入到 pq 里面
if (node.next != null) {
pq.offer(node.next);
}
}
return result.next;
}
}