合并 K 个升序链表
Merge k Sorted Lists
本机进度仅保存在当前浏览器
题目描述
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例：lists = [[1, 4, 5], [1, 3, 4], [2, 6]]，输出 [1, 1, 2, 3, 4, 4, 5, 6]。
解题思路
- 小顶堆做法：把 k 个链表头放入堆，每次弹出最小节点接到结果尾部，再把它的 next 入堆，O(N log k)。
- Python 的 heapq 不能直接比较节点，堆元素用 (节点值, 序号, 节点) 三元组回避比较。
- 分治做法同样优秀：两两合并、逐层向上，共 log k 层，每层总代价 O(N)，与堆做法同数量级且常数更小。
参考实现
查看参考实现Python · 建议先自行作答
import heapq
def mergeKLists(lists):
# 小顶堆维护 k 个链表的当前头节点
heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
heapq.heapify(heap)
dummy = tail = ListNode(0)
while heap:
val, i, node = heapq.heappop(heap)
tail.next = node
tail = node
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next