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

LeetCode 21. 合并两个有序链表

news 2026/8/12 19:57:23

一、题目与考点拆解

题目要求

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

输入：两条各自升序排列的单链表
输出：合并后的升序单链表
要求：直接复用原链表节点，不需要新建节点存值

核心考点

这道题真正考察的不是逻辑复杂度，而是链表操作的基本功：

指针的移动与拼接，理解「修改 next 指针就是修改链表结构」
哑节点（哨兵节点）的使用，统一头节点与中间节点的处理逻辑
边界处理：空链表、一条先走完的剩余拼接

最优解为双指针迭代法，时间复杂度 O (n+m)（两条链表各遍历一次），空间复杂度 O (1)（仅用常数个指针变量）。

二、核心思路：哑节点 + 双指针迭代

两条链表本身都是升序的，我们只需要用两个指针分别指向两条链表的当前节点，每次选值更小的节点拼接到结果链表尾部即可。

核心技巧是哑节点（Dummy Node）：先创建一个无业务值的占位头节点，所有节点都统一拼接到它的后面，彻底消除「第一个节点到底属于哪条链表」的特殊判断，代码逻辑极度简洁。

整体流程：

创建哑节点作为结果链表的占位头，用一个尾部指针 cur 永远指向已拼接部分的最后一个节点
同时遍历两条链表，谁的值更小，就把谁的节点接到 cur 后面，对应链表指针后移一步
每次拼接完成后，cur 同步后移一步，永远保持在结果链表尾部
当其中一条链表遍历完毕时，直接把另一条链表的剩余部分整条接到尾部
最终返回哑节点的 next，也就是真正的结果链表头节点

三、最终定稿 AC 代码

class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 哑节点：占位用的空头节点，统一拼接逻辑 ListNode head = new ListNode(); // 尾部指针：永远指向当前已拼接链表的最后一个节点 ListNode cur = head; // 两条链表都不为空时，两两比较拼接 while (list1 != null && list2 != null) { if (list1.val < list2.val) { cur.next = list1; list1 = list1.next; } else { cur.next = list2; list2 = list2.next; } // 尾部指针同步后移 cur = cur.next; } // 收尾：谁还有剩余，直接整条接在末尾 cur.next = list1 != null ? list1 : list2; // 哑节点本身无意义，返回真正的头节点 return head.next; } }

四、逐行深度拆解

1. 初始化：哑节点 + 尾部指针

ListNode head = new ListNode(); ListNode cur = head;

head是哑节点，本身不存储有效数据，只起占位作用。没有哑节点的话，需要单独判断第一个节点来自 list1 还是 list2，单独给结果链表的头赋值，逻辑繁琐且容易出空指针；有了哑节点，所有节点都用cur.next = xxx的统一逻辑拼接。
cur是尾部指针，永远指向已经拼好的链表的最后一个节点，负责承接下一个新节点。初始时和哑节点重合，代表还没有拼接任何有效节点。

2. 循环拼接主体

while (list1 != null && list2 != null) { if (list1.val < list2.val) { cur.next = list1; list1 = list1.next; } else { cur.next = list2; list2 = list2.next; } cur = cur.next; }

循环条件必须是&&：只有两条链表都还有节点时，才继续两两比较；只要有一条走完了，就退出循环。 ❌ 如果写成||，会出现某条链表已经为空还去取 val 的情况，直接空指针异常。
拼接顺序：先把节点接到 cur 后面，再把对应链表的指针往后挪一步。
最容易漏的一行：cur = cur.next接上新节点后，尾部指针必须同步后移，否则下一次拼接会覆盖掉上一个节点，最终结果只剩最后一个节点。这是链表题最高频的手写错误。

3. 收尾：三目运算符拼接剩余链表

cur.next = list1 != null ? list1 : list2;

这是新手最容易疑惑的一行，拆开讲透：

循环退出的必然结果：因为循环条件是两条都不为空才继续，所以退出时一定是「一条已经空了，另一条还有剩余」，不可能两条同时剩，也不会两条同时空（除非输入本身全空）。
为什么能直接整条接：剩余的链表本身就是升序的，且所有节点的值都大于等于已经拼好的节点，不需要再遍历比较，直接整条接上即可。这是链表结构的优势 —— 只改一个 next 指针，就能接上一整段，不需要逐个拷贝。
语法等价：这是 Java 三元运算符，和下面的 if-else 完全等价：
```
if (list1 != null) { cur.next = list1; } else { cur.next = list2; }
```
作用就是判断谁还有剩余，就把谁剩下的整条链表接在结果尾部。

4. 返回结果

return head.next;

head是我们自己创建的哑节点，没有业务意义，真正的结果链表从它的下一个节点开始。 ❌ 新手高频坑：直接返回head，会导致结果多一个无意义的默认值头节点。

五、新手必踩坑清单

坑 1：漏掉`cur = cur.next`

现象：所有节点都被覆盖，最终结果只剩最后一个节点
原因：尾部指针没有同步后移，每次拼接都在同一个位置覆盖

坑 2：直接返回 head 而非 head.next

现象：结果链表开头多了一个值为 0 的无效节点
原因：忘记哑节点只是占位用的，真正的头在它的 next

坑 3：循环条件写成 ||

现象：运行时空指针异常
原因：一条链表走完后还继续访问它的 val，必然报错

坑 4：收尾部分还要写循环逐个拼接

现象：逻辑冗余，代码变长
原因：没利用好链表本身的有序性和指针特性，剩余部分整条拼接即可，无需遍历

坑 5：不用哑节点，单独处理头节点

现象：逻辑分支多，边界判断繁琐，极易出错
原因：没掌握哑节点技巧，链表拼接题优先上哑节点是通用最优解

六、拓展：递归版实现

这道题也有非常简洁的递归写法，核心思想完全一致：选出当前更小的节点，它的 next 等于「两条剩余链表的合并结果」。

class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 递归终止：一条为空，直接返回另一条 if (list1 == null) return list2; if (list2 == null) return list1; if (list1.val < list2.val) { list1.next = mergeTwoLists(list1.next, list2); return list1; } else { list2.next = mergeTwoLists(list1, list2.next); return list2; } } }

递归版代码更短，但递归栈会带来 O (n+m) 的空间开销，面试手写优先推荐迭代版，递归版可作为思路补充。

七、面试相关

口述思路（直接背）

这道题我用迭代法加哑节点来做。首先创建一个哑节点作为结果链表的占位头，用一个指针维护当前尾部，然后同时遍历两条有序链表，每次选择值更小的节点拼接到尾部，对应链表指针后移。当其中一条链表遍历完时，直接把另一条的剩余部分接在尾部，最终返回哑节点的下一个节点。
时间复杂度是 O (n+m)，两条链表各遍历一次；空间复杂度 O (1)，只用到常数个指针变量。