递归与搜索算法实战：汉诺塔、链表与快速幂

注意函数参数中引用传递的使用，这能避免不必要的拷贝开销。实际编写时，重点在于理清递归调用的顺序和辅助柱子的角色切换。

2 合并两个有序链表

题目描述

将两个升序链表合并为一个新的升序链表并返回。

解题过程

利用递归特性，比较两个链表当前节点的值。较小的节点作为新链表的头节点，其 next 指针指向剩余部分合并后的结果。

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

这里的关键是理解 l1->next 的赋值操作实际上是在构建后续节点的连接关系。

3 反转链表

题目描述

给定单链表的头节点 head，请反转整个链表。

解题过程

递归反转的核心在于：假设 reverseList(head->next) 已经完成了剩余部分的反转，那么只需要调整当前节点 head 与其后继节点的指针方向即可。

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

注意最后一步 head->next = nullptr，这是为了防止形成环。

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;
    }
};

这里用 tmp 暂存后续已交换好的链表头，逻辑会清晰很多。

5 Pow(x, n)

题目描述

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

解题过程

暴力枚举时间复杂度为 O(n)，使用快速幂算法可将复杂度降为 O(log n)。核心思想是利用二进制拆分指数，例如 $x^{13} = x^8 \cdot x^4 \cdot x^1$。

算法实现（C++）

class Solution {
public:
    double myPow(double x, int n) {
        // 细节问题：n 可能是负数，转为正数处理
        return n < 0 ? 1.0 / Pow(x, -(long long)n) : Pow(x, n);
    }
    
    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;
    }
};

注意 n 取负数时可能溢出 int 范围，因此内部函数参数需使用 long long。

面试题 08.06. 汉诺塔问题

21. 合并两个有序链表

206. 反转链表

24. 两两交换链表中的节点

50. Pow(x, n)