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 <= 100l1和l2均按非递减顺序排列
📝 核心笔记：合并两个有序链表 (递归法)
1. 核心思想 (一句话总结)
“谁小谁当头，剩下的任务交给下级。”
比较两个链表的头节点，数值小的那个作为当前的头，然后它的 next 指向剩余部分合并后的结果（递归调用）。
💡 直观理解：
只要选出了当前最小的节点，我就不用管剩下的怎么排了，直接把剩下的任务“外包”给递归函数，等它排好序返回给我接上就行。
2. 算法流程 (三步走)
- 判空 (终止条件)：
- 如果
list1空了，没得比了，直接接上list2。 - 如果
list2空了，直接接上list1。
- 如果
- 选头 (比较大小)：
- 看谁更小。假设
list1小，那list1就是老大。
- 看谁更小。假设
- 连接 (递归)：
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)，哪个位置低（数值小）就先把哪个齿轮扣进去，然后往上移一格，继续看下一个。
