【笔面试算法学习专栏】合并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)lstlst.nextvals.sort()# 重建链表...问题时间复杂度O(N log N)但题目要求O(N log k)。对于N很大但k相对小的情况log k log N。二、解法一最小堆Priority Queue2.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))dummyListNode(0)currdummywhileheap:val,i,nodeheapq.heappop(heap)curr.nextnode currcurr.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):ifleftright:returnlists[left]mid(leftright)//2left_listmerge_sort(lists,left,mid)right_listmerge_sort(lists,mid1,right)returnmerge_two(left_list,right_list)defmerge_two(l1,l2):dummyListNode(0)currdummywhilel1andl2:ifl1.vall2.val:curr.nextl1 l1l1.nextelse:curr.nextl2 l2l2.nextcurrcurr.nextcurr.nextl1orl2returndummy.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 如果K1怎么办直接返回该链表。代码中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.valval self.indexindex self.nodenodedef__lt__(self,other):returnself.valother.val# 自定义比较逻辑七、代码模板总结# 最小堆模板importheapqdefmerge_with_heap(lists):heap[(node.val,i,node)fori,nodeinenumerate(lists)ifnode]heapq.heapify(heap)dummycurrListNode(0)whileheap:val,i,nodeheapq.heappop(heap)curr.nextnode currcurr.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》链表章节