题解 | #合并k个已排序的链表#
合并k个已排序的链表
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
合并k个已排序的链表
目标
我们需要把很多条按从小到大排列的珠子串（链表）合并成一条新的珠子串，这条新的珠子串也要按从小到大的顺序排列。
示例
假设我们有三条珠子串：
- 第一条珠子串：
1 → 2 - 第二条珠子串：
1 → 4 → 5 - 第三条珠子串：
6
我们要把这三条珠子串合并成一条新的珠子串，这条珠子串也要按从小到大的顺序排列。
解释步骤
1. 准备一个“假头”珠子
我们先在新珠子串的最前面放一个“假头”珠子，这个珠子实际上不参与最终的珠子串，但可以帮助我们更容易地开始合并。
ListNode dummy = new ListNode(0); // “假头”珠子 ListNode tail = dummy; // 用来记录新珠子串的最后一个珠子
2. 创建一个“魔法盒子”
想象一下，我们有一个“魔法盒子”，这个盒子可以自动把珠子按从小到大的顺序排好。这个“魔法盒子”其实就是一个叫做“优先队列”的工具。
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
3. 把每条珠子串的第一个珠子放进“魔法盒子”
我们从每条珠子串的开头开始，把每条珠子串的第一个珠子放进“魔法盒子”里。
for (ListNode list : lists) {
if (list != null) {
pq.add(list); // 把第一个珠子放进去
}
}
4. 从“魔法盒子”里拿出最小的珠子
我们不断地从“魔法盒子”里拿出最小的珠子，然后把这个珠子放到新珠子串里。
while (!pq.isEmpty()) {
// 从“魔法盒子”里拿出最小的珠子
ListNode minNode = pq.poll();
// 把这个珠子放到新珠子串里
tail.next = minNode;
tail = tail.next;
// 如果这个珠子后面还有珠子，就把后面的珠子也放进“魔法盒子”
if (minNode.next != null) {
pq.add(minNode.next);
}
}
5. 返回新珠子串的头珠子
最后，我们返回新珠子串的第一个珠子（实际上是“假头”珠子的下一个珠子）。
return dummy.next;
示例解析
假设我们有以下三条珠子串：
- 第一条珠子串：
1 → 2 - 第二条珠子串：
1 → 4 → 5 - 第三条珠子串：
6
- 初始化：
- 创建“假头”珠子 dummy。
- 创建“魔法盒子” pq。
- 把每条珠子串的第一个珠子放进“魔法盒子”：1, 1, 6。
- 不断从“魔法盒子”里拿出最小的珠子：
- 取出最小珠子 1，放到新珠子串里，然后检查是否有下一个珠子，如果有则放进“魔法盒子”。
- 再次取出最小珠子 1，放到新珠子串里，然后检查是否有下一个珠子，如果有则放进“魔法盒子”。
- 取出最小珠子 2，放到新珠子串里，然后检查是否有下一个珠子，如果没有则继续。
- 取出最小珠子 4，放到新珠子串里，然后检查是否有下一个珠子，如果有则放进“魔法盒子”。
- 取出最小珠子 5，放到新珠子串里，然后检查是否有下一个珠子，如果没有则继续。
- 取出最小珠子 6，放到新珠子串里，然后检查是否有下一个珠子，如果没有则继续。
- 返回结果：
- 返回合并后的珠子串的头珠子：{1, 1, 2, 4, 5, 6}。
这样，我们就得到了一条新的按从小到大排列的珠子串。
最后附上完整代码
import java.util.PriorityQueue;
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// 创建一个优先队列，按照节点值从小到大排序
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
// 初始化：将所有非空链表的头节点加入优先队列
for (ListNode list : lists) {
if (list != null) {
pq.add(list);
}
}
// 创建虚拟头节点简化边界处理
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
// 只要优先队列不为空，就继续合并
while (!pq.isEmpty()) {
// 取出当前最小的节点
ListNode minNode = pq.poll();
// 将该节点加入到结果链表中
tail.next = minNode;
tail = tail.next;
// 如果该节点有下一个节点，将下一个节点加入优先队列
if (minNode.next != null) {
pq.add(minNode.next);
}
}
// 返回合并后的链表头节点
return dummy.next;
}
}
#牛客创作赏金赛#小学生都能看懂的算法 文章被收录于专栏
主要面向小白的算法文章。以小学生都能看懂为目标而编写，顺便巩固下自己。
