合并两个升序链表
给定两个升序排列的单链表，要求合并成一个新的升序链表并返回头节点。这道题是链表合并的入门题型，掌握它的核心逻辑，才能轻松应对后续的 k 个链表合并。
解题关键：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 即可，无需逐个遍历。
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 实现
/**
* 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 和第 2 个链表得到新链表，再用新链表合并第 3 个，依次类推，直到合并完所有链表。
解题关键
- 空值处理：先判断链表数组是否为空，再过滤数组中的空链表（避免空指针异常），过滤后再次判断是否为空；
- 哨兵节点 + 动态指针：cur 初始指向哨兵节点，且 cur.next 先指向数组第一个链表，作为每轮合并的基础链表；
- 循环合并：for 循环遍历过滤后的链表数组，每轮调用 mergeTwoLists 函数，传入 cur.next 与当前链表，更新合并结果。
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 实现
/**
* 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)。
2. 分治法思路 分治的核心是分而治之：把 k 个链表两两分组，合并后得到 k/2 个链表；再把这 k/2 个链表两两分组，合并后得到 k/4 个；直到最终合并成 1 个链表。
3. 分治法时间复杂度分析 每一轮合并的总耗时都是 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)）。
解题关键：分治递归
- 递归出口：当分治的左边界 = 右边界（left===right），说明只剩一个链表，直接返回；
- 找中点：mid = left + Math.floor((right-left)/2)，避免溢出；
- 拆分：递归拆分左半部分（left→mid）和右半部分（mid+1→right）；
- 合并：调用 mergeTwoLists 合并左右两部分的结果。
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 实现
/**
* 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;
}
}
面试常见问题
-
合并两个链表时，为什么要用哨兵节点？不用的话会有什么问题？ 答：不用哨兵节点需要单独处理'头节点为空'的情况（比如两个链表都为空、或其中一个为空），代码会多出很多边界判断；哨兵节点统一了所有情况，让逻辑更简洁。
-
合并 k 个链表的暴力法和分治法时间复杂度差多少？为什么分治法更优？ 答：暴力法是 O(k²n)，分治法是 O(kn logk)；k 越大差距越明显（比如 k=100，暴力法时间是分治法的 50 倍左右）。分治法通过'两两合并'减少了重复遍历的节点数，每一轮只遍历所有节点一次，轮数是对数级，因此更优。
-
分治法的空间复杂度是多少？能优化吗？ 答：递归版分治法的空间复杂度是 O(logk)（递归栈的深度）；可以用迭代版分治（非递归）把空间复杂度降到 O(1)，但代码会稍复杂。
-
除了分治法，合并 k 个链表还有其他方法吗？ 答：可以用优先队列（小顶堆）：把每个链表的头节点加入堆，每次弹出最小节点，再把该节点的下一个节点加入堆，直到堆为空。时间复杂度也是 O(kn logk)，空间复杂度 O(k)。
-
处理 k 个链表时，为什么要先过滤空链表？ 答：避免空指针异常（比如调用 val 属性时），也能减少无效的合并操作，提升效率。
总结
从'合并两个升序链表'到'合并 K 个升序链表'，核心逻辑始终是'两两合并'，区别只在于'如何组织两两合并的顺序'—— 暴力法是'顺序合并'，分治法是'分组合并'。
这两道题的价值不仅在于解题本身，更在于理解'哨兵节点简化边界''双指针遍历''分治优化时间复杂度'这些通用的算法思想。掌握这些思想，再遇到链表相关的变形题（比如合并有序数组、拆分链表等），也能举一反三。
