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

合并两个有序链表

在处理链表问题时，画图往往是理清指针关系的关键。这道题要求将两个有序链表合并为一个新的有序链表。

思路解析

递归的核心在于定义好基准情况（Base Case）和递归步骤。对于合并操作，我们不需要创建新节点，而是直接复用现有节点的 next 指针。

1. 递归函数的含义：假设函数能帮你把两个链表的头结点之后的部分合并好，返回合并后的头结点。
2. 函数体逻辑：比较当前两个链表的头结点值，选择较小的那个作为合并后链表的当前头结点。然后，将这个较小节点的 next 指向剩余部分的递归结果。
3. 终止条件：当某一个链表为空时，直接返回另一个链表，因为剩下的部分已经是有序的。

注意：链表的题一定要画图，搞清楚指针的操作！

代码实现

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. 函数体逻辑：先把当前结点之后的链表逆序，逆序完之后，把当前结点添加到逆序后的链表末尾即可。
3. 终止条件：当前结点为空或者当前只有一个结点的时候，不用逆序，直接返回。

关键点在于回溯阶段：当递归返回到上一层时，我们需要调整指针方向。head->next->next = head; 这一步是将原后继节点指向当前节点，head->next = nullptr; 则是切断当前节点对原后继的引用，防止成环。