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

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 更小，将其 next 指向剩余部分的合并结果
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
    }
};

总结

递归不是魔法，而是一种解决问题的策略。通过汉诺塔和链表合并的例子可以看出，只要抓住'问题分解'和'信任子问题'这两个核心，就能写出简洁高效的递归代码。在实际开发中，遇到复杂结构问题时，不妨先尝试用递归拆解，往往能获得更优雅的解法。