算法笔记：合并K个升序链表（LeetCode 23）
算法笔记合并K个升序链表LeetCode 23题目描述给你一个链表数组每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中返回合并后的链表。示例输入lists [[1,4,5],[1,3,4],[2,6]]输出[1,1,2,3,4,4,5,6]解释链表数组如下1-4-5, 1-3-4, 2-6合并后得到有序链表1-1-2-3-4-4-5-6数据范围0 k 10^40 lists[i].length 500所有链表节点总数不超过10^4核心前置知识1. 堆Heap堆是满足堆序性质的完全二叉树可以通过下标映射用一维数组高效存储无需额外指针开销。分类大顶堆任意父节点的值 ≥ 左右子节点的值堆顶为全局最大值小顶堆任意父节点的值 ≤ 左右子节点的值堆顶为全局最小值核心操作时间复杂度均为 O(logn)上滤上浮插入元素时将元素放到堆尾不断与父节点比较交换直到满足堆序性质下滤下沉删除堆顶时将堆尾元素移到堆顶不断与子节点比较交换直到满足堆序性质两种建堆方式自上而下逐个插入元素 上滤调整时间复杂度 O(nlogn)自下而上先排成完全二叉树结构从最后一个父节点开始逐个下滤时间复杂度 O(n)2. 优先队列Priority Queue优先队列是抽象数据类型ADT只定义行为规范每个元素带有优先级出队时返回优先级最高或最低的元素不遵循普通队列的「先进先出」规则。最通用实现二叉小顶堆核心操作逻辑弹出最值弹出堆顶元素将堆尾元素移到堆顶后执行下滤调整插入元素将元素放到堆尾后执行上滤调整3. 堆排序Heap Sort基于堆结构的原地比较排序算法是堆数据结构的经典应用。核心原理利用堆「O(1) 获取最值」的特性不断取出最值并调整堆结构最终得到有序序列工程实现细节升序排序通常使用大顶堆实现每次将堆顶最大值与堆尾元素交换缩小堆的有效范围后调整堆结构实现原地排序空间复杂度 O(1)三种解法实现基础工具合并两个升序链表所有解法的底层依赖双指针遍历两条链表按数值大小依次拼接节点。// 合并两个升序链表publicListNodemerge2List(ListNodel1,ListNodel2){if(l1null||l2null){returnl1null?l2:l1;}ListNodedummynewListNode();ListNodepdummy;while(l1!nulll2!null){if(l1.vall2.val){p.nextl1;l1l1.next;}else{p.nextl2;l2l2.next;}pp.next;}p.nextl1!null?l1:l2;returndummy.next;}解法一逐一顺序合并思路依次将结果链表与数组中的每一条链表合并复用双链表合并的逻辑。复杂度分析时间复杂度O(k²n)。第一次合并长度 n第二次 2n…第 k 次 kn总和为 n*(12…k) nk(k1)/2空间复杂度O(1)原地修改节点指针代码实现publicListNodemergeOneByOne(ListNode[]lists){if(listsnull||lists.length0){returnnull;}ListNoderesnull;for(ListNodel:lists){resmerge2List(res,l);}returnres;}解法二分治两两合并思路借鉴归并排序的分治思想将链表数组二分递归合并左右区间最终将两个大的有序链表合并。复杂度分析时间复杂度O(kn · logk)。每一轮合并的总节点数为 kn共 logk 轮合并空间复杂度O(logk)递归调用栈的深度代码实现publicListNodemergeDivideConquer(ListNode[]lists){if(listsnull||lists.length0){returnnull;}returnmergeRecursion(lists,0,lists.length-1);}// 递归合并区间 [left, right] 内的所有链表privateListNodemergeRecursion(ListNode[]lists,intleft,intright){if(leftright){returnlists[left];}intmidleft(right-left)/2;ListNodeleftPartmergeRecursion(lists,left,mid);ListNoderightPartmergeRecursion(lists,mid1,right);returnmerge2List(leftPart,rightPart);}解法三最小堆优先队列实现思路维护一个大小为 k 的小顶堆初始将所有非空链表的头节点入堆。每次弹出堆顶最小值节点拼接到结果尾部再将该节点的后继节点入堆直到堆为空。复杂度分析时间复杂度O(kn · logk)。每个节点入堆、出堆各一次每次堆操作复杂度为 O(logk)空间复杂度O(k)优先队列的最大空间占用代码实现publicListNodemergeByPriorityQueue(ListNode[]lists){QueueListNodeminHeapnewPriorityQueue((v1,v2)-Integer.compare(v1.val,v2.val));// 所有非空链表的头节点入堆for(ListNodenode:lists){if(node!null){minHeap.offer(node);}}ListNodedummynewListNode();ListNodecurdummy;while(!minHeap.isEmpty()){ListNodeminNodeminHeap.poll();cur.nextminNode;curcur.next;// 当前节点的后继入堆参与下一轮最小值竞争if(minNode.next!null){minHeap.offer(minNode.next);}}returndummy.next;}踩坑复盘1. 逐一合并初始值错误错误写法ListNode res new ListNode();会创建一个 val-1 的无效节点导致结果链表头部多出脏数据正确写法初始值设为nullmerge2List天然支持 null 入参直接返回另一条链表2. 复用原节点导致环形链表死循环问题现象连续调用多种解法时第一个方法执行后原始链表结构被篡改后续方法遍历出现死循环根本原因merge2List属于原地合并直接修改原节点的 next 指针会破坏输入的原始链表结构多次复用同一份测试用例会形成环形链表解决方案单次调用解法可正常使用原地合并空间效率更高多次复用同一份用例时每次调用前重新构造独立链表或改为创建新节点的非原地合并3. 优先队列比较器隐患错误写法(v1,v2) - v1.val - v2.val数值过大时可能发生整数溢出包装类型下还存在空指针风险规范写法Integer.compare(v1.val, v2.val)安全无溢出兼容性更强完整可运行源码packagesf;importjava.util.PriorityQueue;importjava.util.Queue;publicclassmergeLinkList{publicstaticclassListNode{ListNodenext;Integerval;ListNode(){this.nextnull;this.val-1;}ListNode(ListNodenext,Integerval){this.nextnext;this.valval;}ListNode(intval){this.valval;this.nextnull;}}// 合并两个升序链表publicListNodemerge2List(ListNodel1,ListNodel2){if(l1null||l2null){returnl1null?l2:l1;}ListNodehnewListNode();ListNodeph;while(l1!nulll2!null){if(l1.vall2.val){p.nextl1;l1l1.next;}else{p.nextl2;l2l2.next;}pp.next;}if(l1!null)p.nextl1;if(l2!null)p.nextl2;returnh.next;}// 解法1逐一顺序合并publicListNodemerge121(ListNode[]list){if(listnull||list.length0){returnnull;}ListNoderesnull;for(ListNodel:list){resmerge2List(res,l);}returnres;}// 解法2分治两两合并递归publicListNodemerge(ListNode[]list,intl,intr){if(lr)returnlist[l];intmidl(r-l)/2;ListNodel1merge(list,l,mid);ListNodel2merge(list,mid1,r);returnmerge2List(l1,l2);}publicListNodemerge22(ListNode[]list){if(listnull||list.length0)returnnull;returnmerge(list,0,list.length-1);}// 解法3小根堆优先队列publicListNodemergePQ(ListNode[]list){QueueListNodepqnewPriorityQueue((v1,v2)-Integer.compare(v1.val,v2.val));for(ListNodenode:list){if(node!null){pq.offer(node);}}ListNodehnewListNode();ListNodeph;while(!pq.isEmpty()){ListNodetpq.poll();p.nextt;pp.next;if(t.next!null){pq.offer(t.next);}}returnh.next;}// 打印链表工具privatestaticvoidprintList(ListNodehead){ListNodecurhead;while(cur!null){System.out.print(cur.val);if(cur.next!null){System.out.print( - );}curcur.next;}System.out.println();}publicstaticvoidmain(String[]args){// 构造测试用例ListNode[]listsnewListNode[3];lists[0]newListNode(1);lists[0].nextnewListNode(4);lists[0].next.nextnewListNode(5);lists[1]newListNode(1);lists[1].nextnewListNode(3);lists[1].next.nextnewListNode(4);lists[2]newListNode(2);lists[2].nextnewListNode(6);// 单解法调用测试printList(newmergeLinkList().mergePQ(lists));}}
