递归与回溯算法实战：汉诺塔、链表操作及快速幂

注：如果是笔试且仅需最终状态，直接赋值 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. 反转链表

题目描述

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

解题过程

递归地将链表尾部反转，然后调整指针方向。注意处理空节点和尾节点的边界情况。

算法实现（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)

题目描述

实现 pow(x, n)，即计算 x 的 n 次幂函数。

解题过程

利用快速幂算法，将时间复杂度从 O(n) 降低到 O(log n)。核心思想是二分法：x^n = (x^(n/2))^2。

算法实现（C++）

class Solution {
public:
    double myPow(double x, int n) {
        // 细节问题：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;
    }
};

以上涵盖了递归与回溯算法的几个经典场景。掌握这些模式后，面对类似的分治或状态搜索问题会有更清晰的思路。