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

合并两个有序链表

思路解析

这道题用递归处理非常直观。核心思想是'分治'：假设我们已经知道如何合并剩余部分，那么只需要比较当前两个头结点的值，把小的那个拿出来作为当前结果的头，剩下的交给递归函数去处理。

关键点在于递归终止条件：当其中一个链表为空时，直接返回另一个链表。这避免了空指针访问。实际写的时候，记得画图理清指针指向，尤其是 next 指针的重新赋值。

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;
        }
    }
};

反转链表

思路解析

反转链表是递归的经典应用。我们要做的其实是把链表从后往前'拨动'指针。

递归函数的定义是：传入一个头结点，返回逆序后的新头结点。逻辑上，先递归反转 head->next 之后的部分，拿到新的头结点 newHead。此时 head->next 已经是反转部分的尾节点了，所以让 head->next->next = head，然后断开 head->next 防止成环。

注意边界条件：如果头结点为空或者只有一个节点，本身就是有序的，直接返回。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
         newHead;
    }
};