题目
给定 k 条已经按升序排列的链表，将它们合并成一条升序链表并返回合并后的头结点。
示例：
输入：
A: 1 → 4 → 5 → null
B: 1 → 3 → 4 → null
C: 2 → 6 → null
输出：
1 → 1 → 2 → 3 → 4 → 4 → 5 → 6 → null解题思路
每一步都需要从 k 个链表的当前头结点中选出最小的那个，所以核心问题是如何高效地找到最小值。
为什么用小顶堆？
- 朴素做法：每次扫描 k 个头结点找最小值，单次操作 O(k)，总时间 O(N·k)
- 小顶堆优化：取最小值 + 插入新节点，单次操作 O(log k)，总时间 O(N·log k)
算法流程
- 将 k 个链表的头结点放入小顶堆
- 从堆中取出最小节点，接到结果链表尾部
- 如果该节点有后继，将后继节点放入堆
- 重复步骤 2-3 直到堆为空
核心不变量
堆里永远只存储”每条链表的当前头结点”，所以堆的大小始终 ≤ k。
代码实现
import java.util.PriorityQueue;
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// 边界处理
if (lists == null || lists.length == 0) {
return null;
}
// pq: 小顶堆，存储各链表的当前头结点，按 val 升序排列
PriorityQueue<ListNode> pq =
new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
// 将每条非空链表的头结点放入堆中
for (ListNode node : lists) {
if (node != null) {
pq.offer(node);
}
}
// dummy: 虚拟头结点，用于固定返回位置
// cur: 移动指针，负责构建新链表
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (!pq.isEmpty()) {
// 取出当前堆中最小节点
ListNode node = pq.poll();
cur.next = node;
cur = cur.next;
// 如果该节点还有后继节点，将其入堆继续比较
if (node.next != null) {
pq.offer(node.next);
}
}
return dummy.next;
}
}代码解释
- 边界处理：如果输入为空或长度为 0，直接返回 null
- 创建小顶堆：使用 PriorityQueue 并提供比较器，按节点值升序排列
- 初始化堆：遍历所有链表，将非空头结点放入堆
- 创建虚拟头：dummy 节点固定返回位置，cur 用于移动
- 主循环：每次从堆中取最小节点，接到结果链表，如有后继则入堆
- 返回结果：返回 dummy.next（跳过虚拟头）
执行过程示例
以示例输入为例：
初始化堆：
heap: [1(A), 1(B), 2(C)]
ans : dummy → null
↑
cur
第1步：取出 1(A)，将 4(A) 入堆
heap: [1(B), 2(C), 4(A)]
ans : dummy → 1 → null
↑
cur
第2步：取出 1(B)，将 3(B) 入堆
heap: [2(C), 3(B), 4(A)]
ans : dummy → 1 → 1 → null
↑
cur
...依此类推速记
小顶堆维护 k 个链表头，每次取最小接到结果链表，再将该节点的 next 放回堆，重复直到堆空。
注意点
- 必须提供比较器：
PriorityQueue<ListNode>必须传入 Comparator，否则编译报错 - 入堆前判空：
if (node != null)避免空指针入堆 - 返回 dummy.next：不是返回 dummy 本身
- 判断后继是否为空：
if (node.next != null)再入堆，避免空节点入堆
复杂度分析
- 时间复杂度：O(N log k)，其中 N 为所有节点总数，每个节点入堆出堆各一次，每次操作 O(log k)
- 空间复杂度：O(k)，堆中最多同时存储 k 个节点