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

流程解析

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 的头节点更小，则将 list2->next 和 list1 放入该函数中实现两个链表的合并
            // 我相信函数能帮我实现出来，这也就是宏观视角看待递归
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        } else {
            // 同理 list1 的头节点更小也是如此
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
    }
};

流程解析

结语

通过汉诺塔和合并有序链表这两个案例，我们可以看到递归的强大之处。理解递归的关键在于建立'相信函数功能'的宏观视角，避免陷入递归展开的细节泥潭。希望这些内容能帮助你更好地掌握递归算法。