当前位置：首页 > news >正文

Leetcode 13 java

news 2025/8/6 10:21:19

21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列1

1 我的想法：

看到这个题目我感觉链表的意味不是很强呢？我感觉就是集合，然后排序一下，可能是因为我写的java和python比较多（当然这题用java写），说不定c里面会用这个链表指针...我不知道怎么写这道题。伤心。我是猪！

2 对你想法的评价

你的想法有一定道理，但只看到了问题的 “结果” 而没抓住 “过程” 的核心哦。

从结果上看，两个升序链表合并后确实是所有元素的升序集合，直接取所有元素排序也能得到答案。
但这种思路忽略了 “链表” 这种数据结构的特性 ——链表的节点是通过指针（或引用）连接的，我们需要通过操作指针来拼接节点，而不是先提取元素再重新创建节点（虽然在 Python/Java 中可以这么做，但这不是链表题考察的核心能力）。
这道题的关键是练习如何利用链表的 “有序性” 高效合并（时间复杂度可以做到 O (n+m)，n 和 m 是两个链表的长度），而如果先提取元素再排序，时间复杂度会变成 O ((n+m) log (n+m))，虽然对于题目中 “节点数≤50” 的规模影响不大，但违背了链表题的考察初衷。

所以呀，你不是 “猪”，只是暂时没从链表的角度思考问题～

下面我用通俗的语言讲讲正确的解法。

题目解法：链表的 “双指针合并”

核心思路

想象两个链表是两列按身高排队的人，l1 是第一列，l2 是第二列，每个人手里都拿着一张写有自己身高的纸条（val），且每个人后面都跟着下一个人（next 指针）。我们要做的是把这两列人合并成一列，且保持按身高从小到大排列。

怎么合并呢？

用两个 “指针”（可以理解为两个 “手指”）分别指向两列的第一个人（p1 指向 l1 头，p2 指向 l2 头）。
每次比较两个指针指向的人的身高，把矮的那个人拉到新队伍里，然后移动对应列的指针（比如 p1 指向的人矮，就把他放进新队伍，然后 p1 移到下一个人）。
重复这个过程，直到其中一列的人全部被拉走，再把剩下那列的人直接接到新队伍后面（因为剩下的人已经是升序的了）。

具体步骤（用 Java 举例）

创建 “哨兵节点”：
新链表需要一个头节点，但一开始不知道头节点是 l1 的第一个还是 l2 的第一个，所以先创建一个 “哨兵”（比如叫 dummy），它的 next 才是真正的头节点。这样能避免处理空链表的特殊情况，简化代码。
初始化指针：
- p1 指向 l1 的头节点（第一列第一个人）。
- p2 指向 l2 的头节点（第二列第一个人）。
- cur 指向 dummy（当前新队伍的末尾，用来接新的人）。
循环比较并拼接：
当 p1 和 p2 都不为空（两列都还有人）时：
- 如果 p1.val <= p2.val：把 p1 接到 cur 后面（cur.next = p1），然后 p1 移到下一个（p1 = p1.next）。
- 否则：把 p2 接到 cur 后面（cur.next = p2），然后 p2 移到下一个（p2 = p2.next）。
- 每次接完后，cur 也要移到新队伍的末尾（cur = cur.next）。
处理剩余节点：
当其中一列的人全部接完后（比如 p1 为空），直接把另一列剩下的人接到 cur 后面（cur.next = p2）。
返回结果：
新链表的头节点是 dummy.next（因为 dummy 只是哨兵）。

举例说明（对应示例 1：l1=[1,2,4]，l2=[1,3,4]）

初始：p1 指 1，p2 指 1，cur 指 dummy。
第一次比较：1 vs 1 → 接 p1，cur 移到 1（dummy→1），p1 移到 2。
第二次比较：2 vs 1 → 接 p2，cur 移到 1（dummy→1→1），p2 移到 3。
第三次比较：2 vs 3 → 接 p1，cur 移到 2（dummy→1→1→2），p1 移到 4。
第四次比较：4 vs 3 → 接 p2，cur 移到 3（dummy→1→1→2→3），p2 移到 4。
第五次比较：4 vs 4 → 接 p1，cur 移到 4（dummy→1→1→2→3→4），p1 为空。
剩余 p2 指 4，接上去：cur.next = 4，最终链表为 1→1→2→3→4→4。

Java 代码实现

java

运行

// 链表节点的定义（题目已给出）
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 l1, ListNode l2) {// 哨兵节点ListNode dummy = new ListNode(-1);ListNode cur = dummy; // 当前新链表的末尾ListNode p1 = l1, p2 = l2;while (p1 != null && p2 != null) {if (p1.val <= p2.val) {cur.next = p1; // 接p1p1 = p1.next;  // p1后移} else {cur.next = p2; // 接p2p2 = p2.next;  // p2后移}cur = cur.next; // cur后移到新末尾}// 接剩余节点cur.next = (p1 == null) ? p2 : p1;return dummy.next; // 哨兵的下一个才是头节点}
}

总结

这个解法的关键是利用两个指针 “同步遍历” 两个有序链表，每次选较小的节点拼接，充分利用了链表的有序性，效率很高。理解了这个思路，以后遇到 “合并 k 个有序链表” 等问题也能举一反三啦～是不是没那么难？加油！

3 详细解法

首先：链表节点的定义（题目自带的，先看懂这个）

java

运行

// 定义链表的节点结构
class ListNode {int val;          // 节点存储的值ListNode next;    // 指向下一个节点的引用（指针）// 三个构造方法，用于创建节点ListNode() {}                     // 空构造ListNode(int val) { this.val = val; }  // 只传值的构造ListNode(int val, ListNode next) {    // 传值和下一个节点的构造this.val = val;this.next = next;}
}

方法一：递归法（逐行注释）

java

运行

class Solution {// 方法：合并两个升序链表，返回合并后的链表头public ListNode mergeTwoLists(ListNode l1, ListNode l2) {// 情况1：如果l1是空链表，直接返回l2（因为没东西可合并了）// 比如l1=null，l2=[1,2]，合并结果就是[1,2]if (l1 == null) {return l2;} // 情况2：如果l2是空链表，直接返回l1（同理）// 比如l2=null，l1=[3,4]，合并结果就是[3,4]else if (l2 == null) {return l1;} // 情况3：两个链表都不为空，比较头节点的值// 如果l1的头节点值更小else if (l1.val < l2.val) {// 重点：l1的下一个节点，应该是l1剩下的部分（l1.next）和l2合并的结果// 相当于先确定当前用l1的头节点，剩下的交给递归处理l1.next = mergeTwoLists(l1.next, l2);// 此时l1就是合并后链表的头节点，返回它return l1;} // 情况4：l2的头节点值更小（或相等）else {// 同理：l2的下一个节点，应该是l1和l2剩下的部分（l2.next）合并的结果l2.next = mergeTwoLists(l1, l2.next);// 此时l2就是合并后链表的头节点，返回它return l2;}}
}

递归法的通俗理解：
就像剥洋葱，每次只处理最外层（两个链表的头节点），里面的部分用同样的方法处理。比如合并[1,3]和[2,4]：

先比较 1 和 2，选 1，剩下的问题是合并[3]和[2,4]
比较 3 和 2，选 2，剩下的问题是合并[3]和[4]
比较 3 和 4，选 3，剩下的问题是合并null和[4]
遇到 null，返回[4]，然后一层层拼接回去，最终得到[1,2,3,4]

方法二：迭代法（逐行注释）

java

运行

class Solution {// 方法：合并两个升序链表，返回合并后的链表头public ListNode mergeTwoLists(ListNode l1, ListNode l2) {// 1. 创建哨兵节点（傀儡节点）// 作用：简化头节点的处理，不用纠结合并后的第一个节点是l1还是l2ListNode prehead = new ListNode(-1);  // 值为-1，只是占位，无实际意义// 2. 创建prev指针，用于"搭建"新链表// 初始时指向哨兵节点，之后会不断后移，始终指向新链表的最后一个节点ListNode prev = prehead;// 3. 循环比较两个链表的节点，直到其中一个链表为空// 条件：l1和l2都不为空（还有节点可以比较）while (l1 != null && l2 != null) {// 如果l1的当前节点值 <= l2的当前节点值if (l1.val <= l2.val) {// 把l1的当前节点接到新链表的末尾（prev的后面）prev.next = l1;// l1后移一步，继续处理l1的下一个节点l1 = l1.next;} else {// 否则，把l2的当前节点接到新链表的末尾prev.next = l2;// l2后移一步，继续处理l2的下一个节点l2 = l2.next;}// prev后移一步，始终保持在新链表的末尾（方便接下一个节点）prev = prev.next;}// 4. 处理剩余节点// 循环结束后，l1和l2至少有一个为空，剩下的节点直接接到新链表后面即可// 因为剩下的节点本身就是升序的prev.next = l1 == null ? l2 : l1;// 5. 返回合并后的链表头// 哨兵节点的下一个才是真正的头节点return prehead.next;}
}

迭代法的通俗理解：
就像用两个手指分别指着两个链表的头，每次挑手指下较小的那个节点，接到新链表上，然后移动对应的手指。比如合并[1,3]和[2,4]：

手指 p1 指 1，p2 指 2 → 选 1 接到新链表，p1 移到 3
手指 p1 指 3，p2 指 2 → 选 2 接到新链表，p2 移到 4
手指 p1 指 3，p2 指 4 → 选 3 接到新链表，p1 移到 null（空）
剩下 p2 指 4，直接接到新链表，最终得到[1,2,3,4]

两种方法的总结

方法	核心操作	适合场景
递归法	自己调用自己，分解问题	逻辑简单，代码短（但递归深度有限制）
迭代法	用指针循环，逐步搭建链表	空间效率高，适合所有情况

这两种方法本质上都是 “比较 - 选择” 的过程，因为输入的链表已经是升序的，所以不需要重新排序，只需要按顺序挑选节点即可，效率都很高～

两种方法的核心对比

递归法像是 "分解问题"：

class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if (l1 == null) {return l2;} else if (l2 == null) {return l1;} else if (l1.val < l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;} else {l2.next = mergeTwoLists(l1, l2.next);return l2;}}
}

每次只决定当前哪个节点应该放在前面
剩下的部分交给同样的合并函数去处理
直到遇到空链表这个 "终止条件"
优点是代码异常简洁，符合人类的递归思维
缺点是需要额外的栈空间来保存递归调用

迭代法像是 "逐步构建"：

class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode prehead = new ListNode(-1);ListNode prev = prehead;while (l1 != null && l2 != null) {if (l1.val <= l2.val) {prev.next = l1;l1 = l1.next;} else {prev.next = l2;l2 = l2.next;}prev = prev.next;}// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可prev.next = l1 == null ? l2 : l1;return prehead.next;}
}