递归与链表实战：汉诺塔、链表操作及快速幂详解

提示：如果是笔试中遇到这种纯逻辑题，有时可以直接赋值 c = a;，但在面试或学习中，理解递归过程才是核心。

2 合并两个有序链表

题目描述

给定两个升序链表，将它们合并成一个新的升序链表并返回。

解题思路

利用递归的特性，每次比较两个链表的头节点，较小的那个作为当前结果的头，然后递归处理剩余部分。

算法实现（C++）

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->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

3 反转链表

题目描述

给定单链表的头节点，反转该链表并返回新的头节点。

解题思路

递归反转的核心在于：假设 reverseList(head->next) 已经完成了后续节点的反转，此时只需要将当前节点的 next 指向它自己，并将原 next 的 next 指向当前节点即可。

算法实现（C++）

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 细节问题：找出口，空节点或只有一个节点时直接返回
        if (head == nullptr || head->next == nullptr) return head;

        // 主逻辑：递归反转后续节点
        ListNode* newHead = reverseList(head->next);
        
        // 调整指针方向
        head->next->next = head;
        head->next = nullptr;

        return newHead;
    }
};

4 两两交换链表中的节点

题目描述

给定链表，两两交换其中的节点，并返回交换后的新头节点。

解题思路

宏观角度看，先交换前两个节点，然后递归处理剩下的部分。注意边界条件：如果节点为空或只剩一个节点，则无法交换。

算法实现（C++）

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        // 出口：节点为空或者是个尾节点，就不能交换
        if (head == nullptr || head->next == nullptr) return head;

        // 递归处理后续节点
        auto tmp = swapPairs(head->next->next);
        
        // 交换当前两个节点
        auto ret = head->next;
        head->next->next = head;
        head->next = tmp;

        return ret;
    }
};

5 Pow(x, n)

题目描述

计算 x 的 n 次幂。

解题思路

暴力循环的时间复杂度是 O(n)，对于大数会超时。这里使用快速幂算法（分治法），将时间复杂度降低到 O(log n)。核心思想是 x^n = (x^(n/2))^2，如果 n 是奇数再乘一个 x。

算法实现（C++）

class Solution {
public:
    double myPow(double x, int n) {
        // 处理负数次幂的情况
        return n < 0 ? 1.0 / Pow(x, -(long long)n) : Pow(x, n);
    }

private:
    double Pow(double x, long long n) {
        // 递归出口
        if (n == 0) return 1.0;

        // 递归计算一半
        double tmp = Pow(x, n / 2);
        
        // 根据奇偶性返回结果
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }
};

以上五个题目涵盖了递归在数学问题、数据结构操作及优化算法中的典型应用。掌握这些模式后，面对类似的递归结构题会有更清晰的思路。