合并 K 个升序链表
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1
示例 2
示例 3
模拟答题者思考
1. 我先想暴力：把所有节点值收集到数组里排序，再逐个新建节点串起来——能过，但完全没用「每条链表已有序」这一条件，时间 O(N log N)、额外空间 O(N)。
2. 重复在哪里？每次只需要在 k 条链表的「当前头节点」里找全局最小者接到结果尾部，然后该链表指针前移——这和合并两个有序链表一样，只是候选从 2 个变成 k 个。
3. 朴素做法：依次把 lists[0] 与 lists[1] 合并、再与 lists[2] 合并……复用 #21 的双指针合并，最坏时间 O(kN)（N 为总节点数），k 很大时偏慢。
4. 优化成最小堆：把 k 个头节点放入堆，每次弹出堆顶（全局最小）接到 curr.next，若该节点有后继则把后继入堆——每个节点恰好入堆、出堆一次，时间 O(N log k)。
5. 另一种 O(N log k) 是分治：两两归并像归并排序，但堆解法更直观，且 k 条链表头随时变化时堆天然适配。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
dummy | ListNode* | 定义：哨兵头节点，不存放有效值 维护：始终位于合并结果链表的最前端，统一处理「结果为空」等边界 更新：创建后不再移动，最终返回 dummy.next |
curr | ListNode* | 定义：合并结果链表的尾指针 维护：指向已拼接部分的最后一个节点，新节点总是接在 curr.next更新：每从堆中取出节点并接入后 curr = curr.next |
heap | min-heap | 定义：存放各链表当前头节点的最小堆，堆顶始终是全局最小值 维护：初始化时把每条非空链表的头节点入堆；每弹出一个节点后，若该节点还有后继则把后继入堆 更新： heappop 取出最小节点；heappush(node.next) 补充下一位候选 |
(val, i, node) | tuple | 定义：堆元素的排序键——节点值、链表编号、节点指针 维护：值相等时用编号 i 打破平局，避免 Python 比较两个 ListNode 对象更新：每次入堆时按当前头节点的三元组构造 |
落码步骤
1. 创建哨兵 dummy，curr = dummy；初始化空堆 heap
2. 遍历 lists：对每条非空链表，将 (node.val, i, node) 入堆
3. 当堆非空：弹出最小元 (val, i, node)，挂到 curr.next，curr = curr.next
4. 若 node.next 非空，将 (node.next.val, i, node.next) 入堆
5. 返回 dummy.next
代码实现
import heapq
from typing import List, Optional
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
dummy = ListNode(0) # 哨兵，简化头节点处理
curr = dummy # 结果链表的尾指针
heap: list[tuple[int, int, ListNode]] = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
while heap:
_, i, node = heapq.heappop(heap)
curr.next = node
curr = curr.next
nxt = node.next
if nxt:
heapq.heappush(heap, (nxt.val, i, nxt))
return dummy.nextclass Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
for (ListNode* head : lists) {
if (head) pq.push(head);
}
ListNode dummy(0);
ListNode* curr = &dummy;
while (!pq.empty()) {
ListNode* node = pq.top();
pq.pop();
curr->next = node;
curr = curr->next;
if (node->next) pq.push(node->next);
}
return dummy.next;
}
};
// 时间 O(N log k)，空间 O(k)（堆大小）复杂度分析
O(N log k)
O(k)（堆大小）
常见坑
Python 堆直接存 ListNode：值相等时会比较两个节点对象并报错——必须用 (val, i, node) 元组，用编号 i 打破平局。
忘记移动 curr：只设置 curr.next 却不 curr = curr.next，会导致节点叠在同一位置或成环。
空链表未过滤：初始化时须跳过 null 头节点，否则堆中混入空指针；lists = [] 或 [[]] 应直接返回空链表。
必测边界 Case
lists = [] → []
lists = [[]] → []
lists = [[1,4,5],[1,3,4],[2,6]] → [1,1,2,3,4,4,5,6]（堆须正确处理值相等）