递归算法实战：汉诺塔与合并有序链表详解

流程解析

2. 合并两个有序链表

题目描述

给定两个升序链表，将它们合并成一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

算法思路

递归处理链表的核心在于定义好当前函数的职责：接收两个头结点，返回合并后的头结点。

1. 比较头结点：选择值较小的那个作为合并后链表的当前头结点；
2. 递归剩余部分：将该头结点的 next 指针指向剩余部分的递归结果；
3. 终止条件：当某个链表为空时，直接返回另一个链表。

特别提醒：链表操作务必画图辅助，理清指针指向关系，避免野指针或内存泄漏。

C++ 实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(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) {
            // list2 更小，将其 next 指向剩余部分的合并结果
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        } else {
            // list1 更小，同理
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
    }
};

流程解析

掌握递归的精髓不在于推导每一步的执行栈，而在于明确函数的功能契约。只要找准终止条件和递推关系，就能用简洁的代码解决复杂问题。希望这两道例题能帮你建立起对递归的信心。