C++ 递归实战：合并有序链表与反转链表

合并两个有序链表

在递归处理链表时，核心在于定义好函数的语义。对于合并两个有序链表，我们可以将问题拆解为：比较当前两个节点的值，较小的那个作为结果链表的头，剩下的部分交给递归函数继续处理。

思路解析

1. 基准情况：如果其中一个链表为空，直接返回另一个链表。这是递归的终止条件。
2. 递归步骤：比较 list1 和 list2 的头节点值。假设 list1 较小，那么 list1 就是当前合并后链表的头。接下来，我们需要把 list1->next 和 list2 合并的结果接在 list1 后面。
3. 指针操作：务必画图辅助理解。递归返回的是'剩余部分合并后的头'，我们只需要调整当前节点的 next 指针指向它即可。

C++ 代码实现

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // 基准情况：任一链表为空，返回另一链表
        if (list1 == nullptr) return list2;
        if (list2 == nullptr) return list1;

        // 选择较小的节点作为当前头结点
        if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list2->next, list1);
            return list2;
        }
    }
};

这段代码简洁地体现了分治思想。每次递归调用都缩小了问题规模，直到遇到空指针。实际调试时，建议打印中间状态或画图确认指针指向，避免死循环。

---

反转链表

反转链表是递归的经典应用。它的难点在于回溯阶段如何重新连接节点。

思路解析

1. 递归语义：函数接收一个头节点，返回逆序后的新头节点。
2. 递归过程：先递归处理 head->next 之后的链表。当递归返回时，意味着从第二个节点开始的链表已经反转好了。
3. 回溯连接：此时 head 还是原链表的第二个节点（逻辑上），而 head->next 已经是反转后子链表的尾节点。我们需要让 head->next->next = head，并将 head->next 置空，完成当前节点的翻转。