21. 合并两个有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

简单

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

示例 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. 核心思想 (一句话总结)

“谁小谁当头，剩下的任务交给下级。”

比较两个链表的头节点，数值小的那个作为当前的头，然后它的 next 指向剩余部分合并后的结果（递归调用）。

💡 直观理解：

只要选出了当前最小的节点，我就不用管剩下的怎么排了，直接把剩下的任务“外包”给递归函数，等它排好序返回给我接上就行。

2. 算法流程 (三步走)

1. 判空 (终止条件)：

• • 如果list1空了，没得比了，直接接上list2。
  • 如果list2空了，直接接上list1。

1. 选头 (比较大小)：

• • 看谁更小。假设list1小，那list1就是老大。

1. 连接 (递归)：

• • list1的后面 (next) 应该接谁？接 “list1剩余部分” 和 “list2完整部分” 合并后的结果。

🔍 代码回忆清单

// 题目：LC 21. 合并两个有序链表 class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 1. 终止条件 (底线) // 只要有一条链表空了，就直接返回另一条 (另一条也是有序的，直接接上) if (list1 == null) return list2; if (list2 == null) return list1; // 2. 递归主逻辑 (选老大) if (list1.val < list2.val) { // list1 小，list1 当头 // list1 的下家是谁？ -> 是 (list1.next 和 list2) PK 出来的赢家 list1.next = mergeTwoLists(list1.next, list2); return list1; // 别忘了返回当前的头 } else { // list2 小 (或相等)，list2 当头 // list2 的下家是谁？ -> 是 (list1 和 list2.next) PK 出来的赢家 list2.next = mergeTwoLists(list1, list2.next); return list2; } } }

⚡ 快速复习 CheckList (易错点)

• [ ]终止条件写全了吗？必须处理list1 == null和list2 == null两种情况。
• [ ]返回值是谁？返回的是当前被选中的那个较小的节点（即当前的头）。
• [ ]空间复杂度？递归法是 $O(N+M)$，因为消耗了栈空间。如果面试官要求 $O(1)$ 空间，需要改用迭代法(Dummy Node)。
• [ ]相等怎么处理？代码中else处理了大于等于的情况，相等时选list2，这没问题，依然保持有序。

🖼️ 场景联想

拉拉链。

拉链的锁头就是递归函数。

它看着左边齿轮 (list1) 和右边齿轮 (list2)，哪个位置低（数值小）就先把哪个齿轮扣进去，然后往上移一格，继续看下一个。