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

合并两个有序链表

题目描述： 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

算法思路： 这道题用递归处理非常直观。核心逻辑在于比较两个链表的当前头结点，值较小的那个作为合并后链表的头结点，然后将其 next 指针指向剩余部分的递归结果。

具体来说，如果其中一个链表为空，直接返回另一个链表即可。否则，比较 list1 和 list2 的值：

• 若 list1->val < list2->val，则 list1 是当前头结点，它的下一个节点应该是 mergeTwoLists(list1->next, list2) 的结果。
• 反之亦然。

注意： 链表操作务必画图辅助理解，明确指针的指向变化，避免断链或死循环。

代码实现（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;
        }
    }
};

---

反转链表

题目描述： 给定单链表的头结点 head，请反转链表并返回新的头结点。