合并两个升序链表 与 合并k个升序链表

玩转链表合并✨：从 2 个到 k 个升序链表的通关秘籍

在算法面试的高频题库里，链表相关题目一直是 “常客”，而 “升序链表合并” 更是其中的经典题型 —— 从基础的「合并两个升序链表」，到进阶的「合并 k 个升序链表」，难度层层递进，却也藏着通用的解题逻辑。今天就带大家拆解这两道题，从核心思路到代码实现，再到面试官常问的 “灵魂拷问”，一次性吃透✨！

leetcode链接：

合并两个有序链表

 合并 K 个升序链表

一、合并两个升序链表：基础版 “链表拼接术” 📌

给定两个升序排列的单链表，要求合并成一个新的升序链表并返回头节点。这道题是链表合并的 “入门款”，掌握它的核心逻辑，才能轻松应对后续的 k 个链表合并。

1. 解题关键：3 个 “核心武器”

想要优雅解决这道题，离不开三个关键设计，少一个都可能让边界处理变得繁琐：

• 🛡️ 哨兵节点（dummy）：值通常设为 - 1（无实际意义），作用是 “简化边界处理”。比如当两个链表都为空、或其中一个为空时，不用单独判断头节点，直接返回dummy.next即可。
• 📌 动态指针（cur）：初始指向哨兵节点，相当于 “拼接工人”，负责把选中的节点接在新链表后面，每拼接一个节点就向后移动一步。
• 🔍 双指针（p1、p2）：分别指向两个链表的当前遍历节点，是 “决策核心”。通过比较p1.val和p2.val，决定该拼接哪个节点，直到其中一个链表遍历完毕。

具体执行逻辑：① 双指针同步遍历，while循环条件是p1和p2都不为空；② 若p1.val ≤ p2.val，把p1接在cur.next，同时p1后移；反之则拼接p2，p2后移；③ 每轮循环结束后，cur后移一步，准备接下一个节点；④ 循环结束后，必有一个链表还有剩余节点（本身有序），直接把剩余链表接在cur.next即可，无需逐个遍历。

2. 代码展示

JS 版本

javascript

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * 合并两个升序有序链表，返回新的升序链表头节点 * @param {ListNode} list1 - 第一个升序有序链表头节点 * @param {ListNode} list2 - 第二个升序有序链表头节点 * @returns {ListNode} 合并后的升序链表头节点 */ var mergeTwoLists = function (list1, list2) { // 哨兵节点（哑节点）：简化空链表等边界情况处理 let dummy = new ListNode(-1); // 动态指针：负责拼接新节点，初始指向哨兵节点 let cur = dummy; // 双指针：分别遍历两个输入链表 let p1 = list1, p2 = list2; // 双指针同步遍历，直到其中一个链表遍历完毕 while (p1 !== null && p2 !== null) { if (p1.val <= p2.val) { // 拼接p1节点，p1指针后移 cur.next = p1; p1 = p1.next; } else { // 拼接p2节点，p2指针后移 cur.next = p2; p2 = p2.next; } // 动态指针后移，准备拼接下一个节点 cur = cur.next; } // 处理剩余节点：直接拼接未遍历完的链表（链表本身有序） cur.next = p1 !== null ? p1 : p2; // 哨兵节点的next是合并后链表的真实头节点 return dummy.next; }; 

JAVA 版本

java

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 哨兵节点（哑节点）：简化边界处理 ListNode dummy = new ListNode(-1); // 动态指针：负责拼接新节点 ListNode cur = dummy; // 双指针：遍历两个输入链表 ListNode p1 = list1, p2 = list2; // 双指针同步遍历，直到其中一个链表遍历完毕 while (p1 != null && p2 != null) { if (p1.val <= p2.val) { // 拼接p1节点，p1后移 cur.next = p1; p1 = p1.next; } else { // 拼接p2节点，p2后移 cur.next = p2; p2 = p2.next; } // 动态指针后移 cur = cur.next; } // 拼接剩余未遍历完的链表 cur.next = p1 != null ? p1 : p2; // 返回合并后链表的真实头节点 return dummy.next; } } 

二、合并 k 个升序链表：进阶版 “分治优化术” 🚀

当链表数量从 2 个变成 k 个，直接套用 “两两合并” 的暴力思路虽然可行，但时间复杂度会飙升。这道题的核心是 “优化时间复杂度”，而分治思想是最优解的关键。

方法一：暴力迭代法（基础版）

1. 解题思路

基于 “合并两个升序链表” 的逻辑，遍历链表数组：先合并第 1 和第 2 个链表得到新链表，再用新链表合并第 3 个，依次类推，直到合并完所有链表。

2. 解题关键

• 🚫 空值处理：先判断链表数组是否为空，再过滤数组中的空链表（避免空指针异常），过滤后再次判断是否为空；
• 🧰 哨兵节点 + 动态指针：cur初始指向哨兵节点，且cur.next先指向数组第一个链表，作为每轮合并的 “基础链表”；
• 🔄 循环合并：for循环遍历过滤后的链表数组，每轮调用mergeTwoLists函数，传入cur.next与当前链表，更新合并结果。

3. 代码展示

JS 版本

javascript

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * 合并k个升序链表（暴力迭代法） * @param {ListNode[]} lists - 升序链表数组 * @returns {ListNode} 合并后的升序链表头节点 */ var mergeKLists = function (lists) { // 判空：链表数组为空直接返回null if (lists.length === 0) return null; // 过滤空链表：避免后续合并时出现空指针 const filterLists = lists.filter(list => list !== null); // 过滤后仍为空，返回null if (filterLists.length === 0) return null; // 哨兵节点：简化边界处理 let dummy = new ListNode(-1); // 动态指针：初始指向第一个链表，作为合并的基础 dummy.next = filterLists[0]; let cur = dummy; // 遍历链表数组，依次合并 for (let i = 1; i < filterLists.length; i++) { // 合并当前基础链表（cur.next）和第i个链表 cur.next = mergeTwoLists(cur.next, filterLists[i]); } // 返回合并后链表头节点 return dummy.next; }; // 复用合并两个升序链表的函数 var mergeTwoLists = function (list1, list2) { let dummy = new ListNode(-1); let cur = dummy; let p1 = list1, p2 = list2; while (p1 !== null && p2 !== null) { if (p1.val <= p2.val) { cur.next = p1; p1 = p1.next; } else { cur.next = p2; p2 = p2.next; } cur = cur.next; } cur.next = p1 !== null ? p1 : p2; return dummy.next; }; 

JAVA 版本

java

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { // 判空：链表数组为空返回null if (lists == null || lists.length == 0) return null; // 过滤空链表 List<ListNode> filterLists = new ArrayList<>(); for (ListNode list : lists) { if (list != null) { filterLists.add(list); } } // 过滤后为空返回null if (filterLists.size() == 0) return null; // 哨兵节点 ListNode dummy = new ListNode(-1); dummy.next = filterLists.get(0); ListNode cur = dummy; // 依次合并链表 for (int i = 1; i < filterLists.size(); i++) { cur.next = mergeTwoLists(cur.next, filterLists.get(i)); } return dummy.next; } // 合并两个升序链表的函数 public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode dummy = new ListNode(-1); ListNode cur = dummy; ListNode p1 = list1, p2 = list2; while (p1 != null && p2 != null) { if (p1.val <= p2.val) { cur.next = p1; p1 = p1.next; } else { cur.next = p2; p2 = p2.next; } cur = cur.next; } cur.next = p1 != null ? p1 : p2; return dummy.next; } } 

方法二：分治优化法 ⚡

暴力迭代法虽然容易理解，但时间复杂度太高，面试中面试官大概率会追问 “如何优化”—— 这时候分治思想就是最优解。

1. 解题思路：先拆后合，降低时间复杂度

① 暴力法时间复杂度分析

假设 k 个链表，每个链表有 n 个节点：

• 第 1 次合并：合并 2 个链表，耗时 O (2n)；
• 第 2 次合并：合并（2n）和 n，耗时 O (3n)；
• …
• 第 k-1 次合并：耗时 O (kn)；总时间：O(2n + 3n + ... + kn) = O(n*k(k+1)/2 -n) ≈ O(k²n)。举例：k=4，n=2 → 总时间≈O (16n)（22 +32 +4*2=18≈16）。

② 分治法思路

分治的核心是 “分而治之”：把 k 个链表两两分组，合并后得到 k/2 个链表；再把这 k/2 个链表两两分组，合并后得到 k/4 个；直到最终合并成 1 个链表。

③ 分治法时间复杂度分析

每一轮合并的总耗时都是 O (kn)（所有节点仅遍历一次），合并轮数是log₂k（比如 k=4，轮数 = 2；k=8，轮数 = 3）。总时间：O(kn logk)。举例：k=4，n=2 → 总时间 = O (242)=O (16)（k 越大差距越明显：k=100，暴力法≈O (10000n)，分治法≈O (200n)）。

2. 解题关键：分治递归

• 📌 递归出口：当分治的左边界 = 右边界（left===right），说明只剩一个链表，直接返回；
• 🎯 找中点：mid = left + Math.floor((right-left)/2)，避免溢出；
• ✂️ 拆分：递归拆分左半部分（left→mid）和右半部分（mid+1→right）；
• 🧩 合并：调用mergeTwoLists合并左右两部分的结果。

3. 代码展示

JS 版本

javascript

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * 合并k个升序链表（分治法） * @param {ListNode[]} lists - 升序链表数组 * @returns {ListNode} 合并后的升序链表头节点 */ var mergeKLists = function (lists) { // 判空 if (lists.length === 0) return null; // 过滤空链表 lists = lists.filter(list => list !== null); // 再次判空 if (lists.length === 0) return null; // 调用分治函数合并 return merge(lists, 0, lists.length - 1); }; // 分治函数：拆分链表数组并合并 var merge = function (lists, left, right) { // 递归出口：只剩一个链表，直接返回 if (left === right) { return lists[left]; } // 计算中点（避免溢出） let mid = left + Math.floor((right - left) / 2); // 递归拆分左半部分 let leftList = merge(lists, left, mid); // 递归拆分右半部分 let rightList = merge(lists, mid + 1, right); // 合并左右两部分 return mergeTwoLists(leftList, rightList); } // 复用合并两个升序链表的函数 var mergeTwoLists = function (list1, list2) { let dummy = new ListNode(-1); let cur = dummy; let p1 = list1, p2 = list2; while (p1 !== null && p2 !== null) { if (p1.val <= p2.val) { cur.next = p1; p1 = p1.next; } else { cur.next = p2; p2 = p2.next; } cur = cur.next; } cur.next = p1 !== null ? p1 : p2; return dummy.next; } 

JAVA 版本

java

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { // 判空 if (lists == null || lists.length == 0) return null; // 过滤空链表 List<ListNode> filterLists = new ArrayList<>(); for (ListNode list : lists) { if (list != null) { filterLists.add(list); } } // 再次判空 if (filterLists.size() == 0) return null; // 调用分治函数 return merge(filterLists, 0, filterLists.size() - 1); } // 分治函数 private ListNode merge(List<ListNode> lists, int left, int right) { // 递归出口：只剩一个链表 if (left == right) { return lists.get(left); } // 计算中点（避免溢出） int mid = left + (right - left) / 2; // 递归拆分左半部分 ListNode leftList = merge(lists, left, mid); // 递归拆分右半部分 ListNode rightList = merge(lists, mid + 1, right); // 合并左右部分 return mergeTwoLists(leftList, rightList); } // 合并两个升序链表 private ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode dummy = new ListNode(-1); ListNode cur = dummy; ListNode p1 = list1, p2 = list2; while (p1 != null && p2 != null) { if (p1.val <= p2.val) { cur.next = p1; p1 = p1.next; } else { cur.next = p2; p2 = p2.next; } cur = cur.next; } cur.next = p1 != null ? p1 : p2; return dummy.next; } } 

面试官会问的 “灵魂拷问” 🤔

1. 合并两个链表时，为什么要用哨兵节点？不用的话会有什么问题？

答：不用哨兵节点需要单独处理 “头节点为空” 的情况（比如两个链表都为空、或其中一个为空），代码会多出很多边界判断；哨兵节点统一了所有情况，让逻辑更简洁。

2. 合并 k 个链表的暴力法和分治法时间复杂度差多少？为什么分治法更优？

答：暴力法是O(k²n)，分治法是O(kn logk)；k 越大差距越明显（比如 k=100，暴力法时间是分治法的 50 倍左右）。分治法通过 “两两合并” 减少了重复遍历的节点数，每一轮只遍历所有节点一次，轮数是对数级，因此更优。

3. 分治法的空间复杂度是多少？能优化吗？

答：递归版分治法的空间复杂度是O(logk)（递归栈的深度）；可以用迭代版分治（非递归）把空间复杂度降到O(1)，但代码会稍复杂。

4. 除了分治法，合并 k 个链表还有其他方法吗？

答：可以用优先队列（小顶堆）：把每个链表的头节点加入堆，每次弹出最小节点，再把该节点的下一个节点加入堆，直到堆为空。时间复杂度也是O(kn logk)，空间复杂度O(k)。

5. 处理 k 个链表时，为什么要先过滤空链表？

答：避免空指针异常（比如调用val属性时），也能减少无效的合并操作，提升效率。

结语 📝

从 “合并两个升序链表” 到 “合并 k 个升序链表”，核心逻辑始终是 “两两合并”，区别只在于 “如何组织两两合并的顺序”—— 暴力法是 “顺序合并”，分治法是 “分组合并”。

这两道题的价值不仅在于解题本身，更在于理解 “哨兵节点简化边界”“双指针遍历”“分治优化时间复杂度” 这些通用的算法思想。掌握这些思想，再遇到链表相关的变形题（比如合并有序数组、拆分链表等），也能举一反三✨。