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 置空，完成当前节点的翻转。
4. 终止条件：当 head 为空或 head->next 为空时，说明只剩一个节点或没有节点，直接返回 head。

C++ 代码实现

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 终止条件：空表或单节点
        if (head == nullptr || head->next == nullptr) return head;

        // 递归反转后续链表，newhead 是新链表的头
        ListNode* newhead = reverseList(head->next);

        // 回溯阶段：调整指针方向
        head->next->next = head;
        head->next = nullptr;

        return newhead;
    }
};

注意这里的 head->next->next = head，这行代码容易让人困惑。它的意思是：原本 head 指向 head->next，现在要让 head->next 指回 head。配合 head->next = nullptr 切断旧链接，就实现了局部反转。

总结

这两道题展示了递归在处理链表结构时的强大之处。关键在于明确递归函数的返回值含义，以及利用栈的回溯特性来修改指针。练习时多画图，理清每一层递归中节点的指向变化，能极大降低理解难度。