LeetCode 23. 合并 K 个升序链表 —— 小顶堆（PriorityQueue）

LeetCode 23. 合并 K 个升序链表 —— 小顶堆（PriorityQueue）

📌 题目链接

• https://leetcode.cn/problems/merge-k-sorted-lists/

💡 解题思路

本题是 21. 合并两个有序链表 的进阶版。

暴力思路（不推荐）

• 两两合并：O(kN)
• 效率低，容易超时

class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length == 0) {
return null;
}
if(lists.length == 1) {
return lists[0];
}
ListNode res = new ListNode();
res = merge(lists[0], lists[1]);
for(int i=2;i<lists.length;i++) {
res = merge(res, lists[i]);
}
return res;
}
public ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode();
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;
}
}

最优思路：小顶堆（优先队列）

核心思想：

每次只取 当前所有链表头部最小的节点

具体做法：

🛠 关键技术点

1️⃣ 使用 PriorityQueue 构建小顶堆

PriorityQueue<ListNode> pq =
new PriorityQueue<>((a, b) -> a.val – b.val);

• Java 默认是最小堆
• 按 val 从小到大排序

2️⃣ 初始化堆

for (ListNode node : lists) {
if (node != null) {
pq.offer(node);
}
}

• 只放非空链表
• 堆中最多同时存在 k 个节点

3️⃣ 动态维护堆

ListNode node = pq.poll();
if (node.next != null) {
pq.offer(node.next);
}

📌 关键点：

• 每取出一个节点，就补一个它的后继节点进堆
• 保证堆中始终是各链表当前的“最小值候选”

🧩 完整代码（Java）

/**
* Definition for singly-linked list.
*/
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// 1. 最小堆（按节点值排序）
PriorityQueue<ListNode> pq =
new PriorityQueue<>((a, b) -> a.val – b.val);

// 2. 所有链表的头结点入堆
for (ListNode node : lists) {
if (node != null) {
pq.offer(node);
}
}

// 3. 构造结果链表
ListNode dummy = new ListNode();
ListNode cur = dummy;

while (!pq.isEmpty()) {
ListNode node = pq.poll();
if (node.next != null) {
pq.offer(node.next);
}
cur.next = node;
cur = cur.next;
}

return dummy.next;
}
}

⏱ 复杂度分析

✅ 总结

• ✅ 最小堆写法 逻辑最清晰、最好写
• ✅ 面试中极其常见，属于必会题
• ⚠️ 若要求 O(1) 空间，可使用 分治法（类似归并排序）

一句话总结：
K 路归并，堆中永远只保留“下一个可能的最小值”。