【笔面试算法学习专栏】合并K个升序链表：堆与分治的完美结合
学习目标
- 理解最小堆（优先队列）在算法中的应用
- 掌握分治思想解决多路合并问题
- 能够分析K路归并的复杂度
- 理解为什么堆比直接两两合并更优
- 为处理海量数据排序问题打下基础
一、问题引入
1.1 题目描述
LeetCode 23：给定k个升序链表数组，将所有链表合并到一个升序链表中。
示例：
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6]约束：
- k = lists.length，范围 [0, 10⁴]
- 每个链表节点数范围 [0, 200]
- 期望时间复杂度：O(N log k)，N为总节点数
1.2 为什么不能直接遍历？
最朴素的做法：把所有节点值放到数组，排序后再建链表。
defmergeKLists_naive(lists):vals=[]forlstinlists:whilelst:vals.append(lst.val)lst=lst.nextvals.sort()# 重建链表...问题：时间复杂度O(N log N)，但题目要求O(N log k)。对于N很大但k相对小的情况，log k < log N。
二、解法一：最小堆（Priority Queue）
2.1 堆的核心思想
堆是一棵完全二叉树，小顶堆保证父节点值 ≤ 子节点值。插入/删除时间复杂度都是O(log k)。
为什么用堆？想象K路赛跑，每条链表是最慢的跑步者队列。堆帮你快速找到"下一位最快要出场的选手"。
2.2 算法步骤
1. 初始化：把每个链表的头节点放入最小堆 2. 循环： a. 弹出堆顶（当前最小节点） b. 将弹出的节点接到结果链表 c. 若该节点有后继，把后继入堆 3. 堆为空时，合并完成2.3 代码实现
importheapqdefmergeKLists(lists):# 边界处理heap=[]fori,nodeinenumerate(lists):ifnode:# (节点值, 链表索引, 节点) - 用索引解决值相同时的比较问题heapq.heappush(heap,(node.val,i,node))dummy=ListNode(0)curr=dummywhileheap:val,i,node=heapq.heappop(heap)curr.next=node curr=curr.nextifnode.next:heapq.heappush(heap,(node.next.val,i,node.next))returndummy.next为什么要用索引i作为第二比较元？因为两个节点val相同时，heapq会尝试比较节点对象，导致类型错误。
2.4 复杂度分析
| 指标 | 分析 |
|---|---|
| 时间复杂度 | O(N log k)，每个节点入堆出堆各一次 |
| 空间复杂度 | O(k)，堆最多存k个元素 |
三、解法二：分治归并
3.1 分治思想
分治算法的经典模式：分解 → 解决 → 合并。
对于K个链表，我们可以用归并排序的思路：
- 每次把问题规模减半
- 直到只剩一个或零个链表
- 两两合并，层层回溯
图示：分治合并过程
[1→4→5] [1→3→4] [2→6] ↓分 ↓分 ↓分 [1→4→5] [1→3→4] [2→6] ↓合并 ↓空 [1→1→3→4→4→5] [2→6] ↓合并 [1→1→2→3→4→4→5→6]3.2 代码实现
defmergeKLists(lists):ifnotlists:returnNonereturnmerge_sort(lists,0,len(lists)-1)defmerge_sort(lists,left,right):ifleft==right:returnlists[left]mid=(left+right)//2left_list=merge_sort(lists,left,mid)right_list=merge_sort(lists,mid+1,right)returnmerge_two(left_list,right_list)defmerge_two(l1,l2):dummy=ListNode(0)curr=dummywhilel1andl2:ifl1.val<=l2.val:curr.next=l1 l1=l1.nextelse:curr.next=l2 l2=l2.nextcurr=curr.nextcurr.next=l1orl2returndummy.next3.3 复杂度分析
| 指标 | 分析 |
|---|---|
| 时间复杂度 | O(N log k)，树高为log k，每层合并N个节点 |
| 空间复杂度 | O(log k)，递归栈深度 |
四、两种解法对比
| 特性 | 最小堆 | 分治归并 |
|---|---|---|
| 时间复杂度 | O(N log k) | O(N log k) |
| 空间复杂度 | O(k) | O(log k) |
| 代码复杂度 | 中等 | 较简单 |
| 适用场景 | 数据流式输入 | 已知全部数据 |
| 优点 | 内存稳定 | 递归简洁 |
面试建议：两种都能讲明白最佳。如果时间紧，分治更容易实现无误。
五、扩展：多路归并在工程中的应用
5.1 海量日志排序
假设有1000个文件，每个文件内部有序，但整体无序。如何高效合并？
思路：每次从1000个文件各读一行，放到最小堆，取出最小的写入输出文件，再从该文件补充一行。
5.2 外部排序
当数据量远超内存时，最小堆是外部排序的核心算法。
# 简化的外部排序思路defexternal_sort(input_files,output_file):# 1. 分批次读入内存，排序，写入临时文件# 2. 每次从各临时文件读取一块到内存# 3. 用最小堆合并，输出到最终文件pass六、面试中的延伸问题
6.1 如果K=1怎么办？
直接返回该链表。代码中if not lists已处理。
6.2 如果某链表为空怎么办？
在初始化堆时跳过空链表：if node: heapq.heappush(...)
6.3 如何做到O(N)时间复杂度？
不可能。因为我们需要对N个元素进行排序，最优是O(N log N)。K路归并的O(N log k)已经是在"已知各链表有序"这个先验信息下的最优解。
6.4 进阶：如何支持自定义比较规则？
classNode:def__init__(self,val,index,node):self.val=val self.index=index self.node=nodedef__lt__(self,other):returnself.val<other.val# 自定义比较逻辑七、代码模板总结
# 最小堆模板importheapqdefmerge_with_heap(lists):heap=[(node.val,i,node)fori,nodeinenumerate(lists)ifnode]heapq.heapify(heap)dummy=curr=ListNode(0)whileheap:val,i,node=heapq.heappop(heap)curr.next=node curr=curr.nextifnode.next:heapq.heappush(heap,(node.next.val,i,node.next))returndummy.next八、总结
合并K个有序链表展示了两种经典算法思想：
- 堆：始终维护"当前最小"，适合数据流式处理
- 分治：化繁为简，将K路问题分解为log k层两路合并
面试加分项：
- 解释为什么不用朴素O(N log N)排序
- 分析空间复杂度差异
- 举一反三到外部排序、海量数据处理
习题
- LeetCode 21：合并两个有序链表（基础，必须熟练）
- LeetCode 147：对链表进行插入排序
- LeetCode 148：链表的归并排序（原地排序）
- 思考：如何用最小堆求第K小的数？
参考文献
- LeetCode 23. Merge k Sorted Lists
- 《算法导论》第六章：堆排序
- 《剑指Offer》链表章节