LeetCode 23. 合并K个升序链表——优先队列的经典应用与堆的手动实现
LeetCode 23. 合并K个升序链表——优先队列的经典应用与堆的手动实现
适读人群：Java 中级工程师、备战面试的同学 | 阅读时长：约25分钟 | 难度：困难
开篇故事
从这篇开始，我们进入第二个主题：优先队列与堆。
合并K个升序链表是我在面试里被考烂了的题，几乎每家大厂都会考。它的解法分布非常典型：暴力、分治、优先队列三个层次，分别对应三种技术深度。
很多同学能写出优先队列的解法，但如果面试官追问「你能手写一个堆吗？」「这个优先队列内部是怎么实现的？」就哑了。这篇文章我会在讲完三种解法之后，额外附上一个手动实现的最小堆，让你做到不只会用，还能讲清楚原理。
一、题目解析
题目描述：
给你一个链表数组，每个链表都已经按升序排列。将所有链表合并到一个升序链表中，返回合并后的链表。
示例：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]约束：
k == lists.length0 <= k <= 10^4- 每个链表节点数在
[0, 500]范围内 - 节点值在
[-10^4, 10^4]
核心问题： 每次找 k 个链表头部节点中最小的，接到结果链表上，然后该链表指针后移。
二、解法一：暴力收集排序
思路分析
最简单的想法：把所有节点的值收集到数组里，排序，重新构建链表。
import java.util.*;
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
List<Integer> vals = new ArrayList<>();
// 收集所有节点的值
for (ListNode head : lists) {
while (head != null) {
vals.add(head.val);
head = head.next;
}
}
// 排序
Collections.sort(vals);
// 重建链表
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
for (int val : vals) {
cur.next = new ListNode(val);
cur = cur.next;
}
return dummy.next;
}
}复杂度分析
- 时间复杂度：O(N log N)。N 是节点总数，排序 O(N log N)。
- 空间复杂度：O(N)。存储所有节点值。
三、解法二：分治合并（两两归并）
思路分析
把 K 个链表两两配对合并，每轮处理后链表数量减半，共 log K 轮，每轮 O(N)，总体 O(N log K)。
这是归并排序思想的延伸。
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
return mergeRange(lists, 0, lists.length - 1);
}
// 分治：合并 lists[left..right]
private ListNode mergeRange(ListNode[] lists, int left, int right) {
if (left == right) return lists[left];
int mid = left + (right - left) / 2;
ListNode l1 = mergeRange(lists, left, mid);
ListNode l2 = mergeRange(lists, mid + 1, right);
return mergeTwo(l1, l2);
}
// 合并两个有序链表
private ListNode mergeTwo(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}复杂度分析
- 时间复杂度：O(N log K)。log K 轮，每轮 O(N)。
- 空间复杂度：O(log K)。递归栈深度。
四、解法三（最优）：优先队列（最小堆）
核心思想
维护一个大小为 K 的最小堆，存每个链表的当前头节点。每次从堆中取出最小节点，接到结果链表，然后把该节点的 next 加入堆（如果不为 null）。
完整代码
import java.util.*;
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
// 最小堆，按节点值排序
PriorityQueue<ListNode> pq = new PriorityQueue<>(
(a, b) -> a.val - b.val
);
// 初始化：把每个链表的头节点入堆（非null）
for (ListNode head : lists) {
if (head != null) {
pq.offer(head);
}
}
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;
}
}手动实现最小堆
面试中如果被要求手写堆：
class MinHeap {
private ListNode[] data;
private int size;
public MinHeap(int capacity) {
data = new ListNode[capacity];
size = 0;
}
public void offer(ListNode node) {
data[size] = node;
size++;
siftUp(size - 1);
}
public ListNode poll() {
ListNode result = data[0];
size--;
data[0] = data[size];
siftDown(0);
return result;
}
public boolean isEmpty() {
return size == 0;
}
private void siftUp(int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (data[parent].val > data[i].val) {
swap(i, parent);
i = parent;
} else {
break;
}
}
}
private void siftDown(int i) {
while (2 * i + 1 < size) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size && data[left].val < data[smallest].val) {
smallest = left;
}
if (right < size && data[right].val < data[smallest].val) {
smallest = right;
}
if (smallest != i) {
swap(i, smallest);
i = smallest;
} else {
break;
}
}
}
private void swap(int i, int j) {
ListNode tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
}复杂度分析
- 时间复杂度：O(N log K)。N 次 poll/offer 操作，每次 O(log K)（堆大小最大为 K）。
- 空间复杂度：O(K)。堆的大小。
五、举一反三
优先队列（堆）是「每次取最值」场景的万能工具：
| 题目 | 用法 |
|---|---|
| 373. 查找和最小K对数字 | 多路归并 + 优先队列 |
| 378. 有序矩阵第K小 | 堆优化 vs 二分 |
| 215. 第K大元素 | 最小堆维护前K大 |
| 295. 数据流中位数 | 双堆维护 |
六、踩坑实录
坑一：Comparator 写 a.val - b.val 可能溢出
节点值范围是 [-10^4, 10^4]，差值范围是 [-2×10^4, 2×10^4]，不会溢出。但如果值范围是 Integer.MIN_VALUE 到 Integer.MAX_VALUE 的通用场景，就必须用 Integer.compare(a.val, b.val)，否则溢出导致比较反向。
// 安全写法
(a, b) -> Integer.compare(a.val, b.val)
// 本题可以用但不推荐习惯
(a, b) -> a.val - b.val坑二：初始化堆时加入 null 节点
空链表的头节点是 null，不能加入堆，否则 NPE：
for (ListNode head : lists) {
if (head != null) { // 必须判 null
pq.offer(head);
}
}坑三：Java PriorityQueue 是最小堆，求最大要反转 Comparator
PriorityQueue 默认是最小堆（poll 返回最小值）。如果需要最大堆：
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);七、总结
合并K个升序链表展示了优先队列最经典的应用场景：K路归并。每次从 K 个候选中取最优，用堆实现 O(log K) 的高效选取。
分治解法 O(N log K) 和堆解法同等复杂度，但堆的空间是 O(K) 而分治是 O(log K)，各有权衡。工程中优先使用 Java 内置的 PriorityQueue，面试中能手写堆的 siftUp 和 siftDown 是加分项。