【递归】——五道经典链表与递归问题的深度解析

解题思路：

我们可以使用递归的方法将问题分解为更小的子问题。
对于 n 个盘子，移动过程如下：
移动上 n-1 个盘子：将顶部的 n-1 个盘子从源柱子（a）移动到辅助柱子（b），使用目标柱子（c）作为辅助。
移动第 n 个盘子：将底部的第 n 个盘子从源柱子（a）直接移动到目标柱子（c）。
移动 n-1 个盘子到目标柱子：将之前移动到辅助柱子（b）的 n-1 个盘子移动到目标柱子（c），使用源柱子（a）作为辅助。

class Solution 
{
public:
    void dfs(vector<int>& a, vector<int>& b, vector<int>& c, int n)
    {
        // 基本情况：如果只有一个盘子，直接将其从初始柱子移动到结果柱子
        if (n == 1)
        {
            c.push_back(a.back()); // 将初始柱子a的最后一个盘子移动到结果柱子c
            a.pop_back(); // 移除初始柱子a上的盘子
            return; // 返回，结束当前递归
        }

        // 递归步骤：
        // 1. 将前n-1个盘子从初始柱子a移动到辅助柱子b
        dfs(a, c, b, n - 1);
        
        // 2. 将第n个盘子从初始柱子a移动到结果柱子c
        c.push_back(a.back()); // 移动最后一个盘子到结果柱子c
        a.pop_back(); // 移除初始柱子a上的盘子
        
        // 3. 将n-1个盘子从辅助柱子b移动到结果柱子c
        dfs(b, a, c, n - 1);
    }

    void hanota(vector<int>& a, vector<int>& b, vector<int>& c) 
    {
        int n = a.size(); // 获取初始柱子a上盘子的数量
        dfs(a, b, c, n); // 调用DFS函数进行移动
    }
};

解题思路：

合并两个有序链表的思路是：首先处理基本情况，如果链表 l1 为空，直接返回 l2；如果 l2 为空，直接返回 l1。接着比较两个链表当前节点的值，选择值较小的节点作为合并结果的一部分，并递归地合并剩余的节点。最终，返回合并后的链表头节点。这种方法确保了新链表的顺序性。

class Solution 
{
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        // 如果第一个链表为空，返回第二个链表
        if (l1 == nullptr) return l2;
        // 如果第二个链表为空，返回第一个链表
        if (l2 == nullptr) return l1;

        // 比较两个链表的当前节点值
        if (l1->val <= l2->val)
        {
            // 将l1的当前节点连接到合并结果中，并递归合并l1的下一个节点和l2
            l1->next = mergeTwoLists(l1->next, l2);
            return l1; // 返回当前节点l1
        }
        else
        {
            // 将l2的当前节点连接到合并结果中，并递归合并l1和l2的下一个节点
            l2->next = mergeTwoLists(l1, l2->next);
            return l2; // 返回当前节点l2
        }
    }
};

递归地反转链表的剩余部分，即调用反转函数处理 head->next。
在返回的过程中，将当前节点的 next 指针指向自己，形成反转的链接。
将当前节点的 next 指针设置为 nullptr，使其成为新的链表尾部。

class Solution 
{
public:
    ListNode* reverseList(ListNode* head) 
    {
        // 基本情况：如果链表为空或只有一个节点，直接返回头节点
        if (!head || !head->next)
            return head;

        // 递归反转后续链表
        ListNode* newhead = reverseList(head->next);
        
        // 反转当前节点与下一个节点的指针
        head->next->next = head; // 将当前节点指向前一个节点
        head->next = nullptr; // 当前节点的next设为nullptr，成为新链表的尾部

        return newhead; // 返回反转后的链表头节点
    }
};

检查链表是否为空（head 为 nullptr）或只有一个节点（head->next 为 nullptr）。如果是，直接返回 head，因为没有需要交换的节点。
保存当前节点的下一个节点 (head->next) 为 ret，这将成为新的头节点。
递归调用 swapPairs 函数，处理当前节点之后的节点，得到交换后的结果。
将 head 的下一个节点的 next 指针指向当前节点 (head)，完成一对节点的交换。
将当前节点的 next 指针指向递归返回的结果，这样形成新的链表结构。
最终返回 ret，即新的头节点，形成新的成对交换链表。

class Solution 
{
public:
    ListNode* swapPairs(ListNode* head) 
    {
        // 基本情况：如果链表为空或只有一个节点，直接返回头节点
        if (head == nullptr || head->next == nullptr) return head;

        // ret保存当前成对交换后的新头节点
        ListNode* ret = head->next; 
        
        // 递归交换后续节点的成对
        ListNode* newnode = swapPairs(head->next->next);
        
        // 进行成对交换
        head->next->next = head; // 将当前节点的下一个节点指向当前节点
        head->next = newnode; // 将当前节点的next指向交换后的节点

        return ret; // 返回新头节点
    }
};

处理负指数：

首先检查指数 n 的符号。如果 n 小于 0，则将其转为正数，并计算 x 的绝对值的 n 次方，然后取其倒数，返回 1.0 / ret。
递归计算：

对于非负的 n，调用辅助函数 Pow(x, n) 进行计算。
在 Pow 函数中，首先处理基本情况：如果 n 为 0，返回 1（任何数的 0 次方为 1）。
分治法：

使用递归将问题分解：
计算 x 的 n / 2 次方，保存结果为 tmp。
如果 n 为偶数，结果为 tmp * tmp；如果 n 为奇数，结果为 tmp * tmp * x。
返回结果：

最终，返回计算得到的结果，完成 x 的 n 次方计算。

class Solution 
{
public:
    double myPow(double x, int n) 
    {
        // 处理负指数的情况
        if (n < 0) 
        {
            double ret = Pow(x, -(long long)n); // 使用正指数计算
            return 1.0 / ret; // 返回结果的倒数
        }
        return Pow(x, n); // 直接计算正指数的情况
    }

    double Pow(double x, long long n)
    {
        // 基本情况：任何数的 0 次方为 1
        if (n == 0) return 1;

        // 递归计算 x 的 n/2 次方
        double tmp = Pow(x, n / 2);
        
        // 如果 n 为偶数，返回 tmp 的平方；如果为奇数，返回 tmp 的平方乘以 x
        return (n % 2 == 0) ? tmp * tmp : tmp * tmp * x;
    }
};