算法思想
递归思想
递归关系(recursive relation),数学和计算机科学中，指函数的定义使用函数本身的方法。recursion常用来描述以自相似的方式重复事物的过程。通俗理解我调用我自己。递归模型：斐波那契序列、河内塔。
本博客<<算法题-合并两个升序链表为一个升序链表>>中，要理解 l1.next = mergeTwoLists(l1.next, l2) 这行代码，需要从递归的本质、链表的连接逻辑以及子问题的定义三个维度入手。以下是详细解释：
一、递归的核心：分解问题为“当前步骤 + 子问题”
递归算法的本质是将原问题分解为规模更小、结构相同的子问题，并通过“解决子问题 + 处理当前步骤”来得到最终结果。在合并两个升序链表中：
- 原问题：合并链表
l1和l2，得到一个新的升序链表。 - 子问题：合并
l1和l2中的“剩余部分”，得到一个升序链表。
关键步骤：
- 比较当前节点：比较
l1和l2的当前节点值，选择较小的节点作为结果链表的当前节点。 - 递归处理剩余部分：将选中节点的
next指针指向“剩余节点的合并结果”（即子问题的解）。
二、l1.next = mergeTwoLists(l1.next, l2) 的具体含义
假设当前递归层中：
l1指向节点 A（值为l1.val），l1.next指向节点 B（值为l1.next.val）。l2指向节点 X（值为l2.val）。
当 l1.val < l2.val 时（即节点 A 的值小于节点 X 的值）：
- 选择当前节点：将节点 A 作为结果链表的当前节点。
- 递归处理剩余部分：由于节点 A 已被使用，剩余需要合并的是
l1.next（节点 B 及后续）和l2（节点 X 及后续）。 - 连接结果：将节点 A 的
next指针指向“剩余部分的合并结果”，即l1.next = mergeTwoLists(l1.next, l2)。
三、通过具体案例理解递归过程
假设输入链表：
l1: 1 → 3 → 5
l2: 2 → 4 → 6
1. 第一层递归：比较 l1.val(1) 和 l2.val(2)
- 由于 1 < 2，选择
l1（节点 1）作为结果链表的头节点。 - 剩余需要合并的是
l1.next(3→5)和l2(2→4→6)。 - 执行
l1.next = mergeTwoLists(l1.next, l2)，即节点1.next = merge(3→5, 2→4→6)。
2. 第二层递归：比较 l1.next.val(3) 和 l2.val(2)
- 由于 3 > 2，选择
l2（节点 2）作为结果链表的当前节点。 - 剩余需要合并的是
l1.next(3→5)和l2.next(4→6)。 - 执行
l2.next = mergeTwoLists(l1.next, l2.next)，即节点2.next = merge(3→5, 4→6)。
3. 第三层递归：比较 l1.next.val(3) 和 l2.next.val(4)
- 由于 3 < 4，选择
l1.next（节点 3）作为结果链表的当前节点。 - 剩余需要合并的是
l1.next.next(5)和l2.next(4→6)。 - 执行
l1.next.next = mergeTwoLists(l1.next.next, l2.next)，即节点3.next = merge(5, 4→6)。
4. 以此类推，直到递归终止（l1 或 l2 为空）
- 最终结果链表为：
1 → 2 → 3 → 4 → 5 → 6。
四、递归的终止条件与回溯过程
- 终止条件：当
l1或l2为空时，直接返回另一个链表（因为空链表与任何链表合并的结果就是另一个链表）。if (l1 === null) return l2; if (l2 === null) return l1; - 回溯过程：递归返回时，每一层的结果会作为上一层的“剩余部分合并结果”被连接。例如，第三层递归返回
3 → 4 → 5 → 6，第二层将节点 2 的next指向该结果，得到2 → 3 → 4 → 5 → 6；第一层将节点 1 的next指向该结果，最终得到完整的1 → 2 → 3 → 4 → 5 → 6。
五、总结：递归的“选择-连接”逻辑
l1.next = mergeTwoLists(l1.next, l2) 这行代码的核心逻辑是：
- 选择：由于
l1.val < l2.val，当前结果链表的节点为l1。 - 连接：将
l1的next指针指向“剩余部分的合并结果”，即l1.next（l1的后续节点）和l2（未使用的l2节点）的合并结果。
通过这种方式，递归会逐层处理链表的每个节点，确保最终结果链表保持升序。关键在于理解“当前节点的 next 指针指向剩余节点的合并结果”这一递归连接逻辑。