【每日算法】LeetCode 23. 合并 K 个升序链表-开发者社区

对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

LeetCode 23. 合并 K 个升序链表

1. 题目描述

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，并返回合并后的链表。

示例 1：

输入：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

示例 2：

输入：lists = [] 输出：[]

示例 3：

输入：lists = [[]] 输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i]按升序排列
lists[i].length的总和不超过10^4

2. 问题分析

在前端开发中，我们经常需要处理多个有序数据流的合并，例如：

多来源数据聚合：从多个API接口获取已排序的数据，需要合并展示
日志合并：多个服务的按时间排序的日志需要合并分析
虚拟列表优化：多个有序数据源合并后渲染长列表

这个问题本质上是多路归并问题，是归并排序的扩展。对于前端开发者来说，理解此问题有助于掌握分治、优先队列等思想，在处理大数据流、实现高效渲染时非常有用。

3. 解题思路

3.1 思路概览

我们有几种主要解决方案：

顺序合并法：依次合并每个链表
分治法：借鉴归并排序思想，两两合并
优先队列（最小堆）法：维护当前所有链表头节点的最小值
暴力解法：将所有节点值收集后排序，再构建链表

从复杂度分析看，优先队列法和分治法是最优解，时间复杂度都是O(Nlogk)，其中N是总节点数，k是链表数量。

3.2 各思路详解

3.2.1 顺序合并法

逐个链表合并，每次合并两个有序链表。简单直观，但效率较低。

3.2.2 分治法

采用归并排序的思想，将k个链表配对并两两合并，重复这一过程直到合并成一个链表。

3.2.3 优先队列法（最优解之一）

维护一个大小为k的最小堆，每次从堆中取出最小节点，将该节点的下一个节点加入堆中，直到堆为空。

3.2.4 暴力解法

收集所有节点值到数组，排序后构建新链表。简单但失去了链表的特性优势。

4. 各思路代码实现

4.1 顺序合并法

/** * 合并两个有序链表 */constmergeTwoLists=(l1,l2)=>{constdummy=newListNode(0);letcur=dummy;while(l1&&l2){if(l1.val<l2.val){cur.next=l1;l1=l1.next;}else{cur.next=l2;l2=l2.next;}cur=cur.next;}cur.next=l1||l2;returndummy.next;};/** * 顺序合并K个链表 */constmergeKLists=function(lists){if(lists.length===0)returnnull;letresult=lists[0];for(leti=1;i<lists.length;i++){result=mergeTwoLists(result,lists[i]);}returnresult;};

4.2 分治法

/** * 分治法合并K个链表 */constmergeKLists=function(lists){if(lists.length===0)returnnull;constmerge=(start,end)=>{if(start===end)returnlists[start];if(start>end)returnnull;constmid=Math.floor((start+end)/2);constleft=merge(start,mid);constright=merge(mid+1,end);returnmergeTwoLists(left,right);};returnmerge(0,lists.length-1);};/** * 迭代版本的分治法 */constmergeKListsIterative=function(lists){if(lists.length===0)returnnull;letinterval=1;constn=lists.length;while(interval<n){for(leti=0;i<n-interval;i+=interval*2){lists[i]=mergeTwoLists(lists[i],lists[i+interval]);}interval*=2;}returnlists[0];};

4.3 优先队列法（最小堆）

/** * 优先队列法（最小堆实现） */classMinHeap{constructor(){this.heap=[];}size(){returnthis.heap.length;}push(node){this.heap.push(node);this.bubbleUp(this.heap.length-1);}pop(){if(this.size()===0)returnnull;constmin=this.heap[0];constlast=this.heap.pop();if(this.size()>0){this.heap[0]=last;this.sinkDown(0);}returnmin;}bubbleUp(index){constnode=this.heap[index];while(index>0){constparentIndex=Math.floor((index-1)/2);constparent=this.heap[parentIndex];if(node.val>=parent.val)break;this.heap[parentIndex]=node;this.heap[index]=parent;index=parentIndex;}}sinkDown(index){constlength=this.size();constnode=this.heap[index];while(true){letleftChildIndex=2*index+1;letrightChildIndex=2*index+2;letswap=null;letleftChild,rightChild;if(leftChildIndex<length){leftChild=this.heap[leftChildIndex];if(leftChild.val<node.val){swap=leftChildIndex;}}if(rightChildIndex<length){rightChild=this.heap[rightChildIndex];if((swap===null&&rightChild.val<node.val)||(swap!==null&&rightChild.val<leftChild.val)){swap=rightChildIndex;}}if(swap===null)break;this.heap[index]=this.heap[swap];this.heap[swap]=node;index=swap;}}}constmergeKLists=function(lists){if(lists.length===0)returnnull;constminHeap=newMinHeap();constdummy=newListNode(0);letcur=dummy;// 将所有链表的头节点加入最小堆for(letlistoflists){if(list){minHeap.push(list);}}// 不断从堆中取出最小节点while(minHeap.size()>0){constnode=minHeap.pop();cur.next=node;cur=cur.next;// 如果该节点还有下一个节点，加入堆中if(node.next){minHeap.push(node.next);}}returndummy.next;};/** * 使用JavaScript内置的优先队列（如果环境支持） */constmergeKListsWithPriorityQueue=function(lists){if(lists.length===0)returnnull;constdummy=newListNode(0);letcur=dummy;// 使用优先队列，按节点值排序constpq=newPriorityQueue({compare:(a,b)=>a.val-b.val});// 初始化优先队列for(letlistoflists){if(list){pq.enqueue(list);}}// 处理队列while(!pq.isEmpty()){constnode=pq.dequeue();cur.next=node;cur=cur.next;if(node.next){pq.enqueue(node.next);}}returndummy.next;};

4.4 暴力解法

/** * 暴力解法 */constmergeKLists=function(lists){constnodes=[];// 收集所有节点值for(letlistoflists){while(list){nodes.push(list.val);list=list.next;}}// 排序nodes.sort((a,b)=>a-b);// 构建新链表constdummy=newListNode(0);letcur=dummy;for(letvalofnodes){cur.next=newListNode(val);cur=cur.next;}returndummy.next;};

5. 各实现思路的复杂度、优缺点对比

方法	时间复杂度	空间复杂度	优点	缺点	适用场景
顺序合并	O(kN)	O(1)	实现简单，无需额外空间	效率低，重复遍历节点多	k较小或链表长度较短
分治法	O(Nlogk)	O(logk)	效率高，递归思路清晰	递归栈空间开销	通用场景，尤其适合链表数量多
优先队列	O(Nlogk)	O(k)	效率高，逻辑清晰	需要维护堆结构	实时数据流处理，k较大
暴力解法	O(NlogN)	O(N)	实现极其简单	破坏链表结构，额外空间大	快速实现，不关心性能