本文设计专题一算法题链接
1 汉诺塔问题
题目描述
汉诺塔是递归思想的经典入门题。规则很简单：有三根柱子 A（起始）、B（辅助）、C（目标）。A 柱上有 n 个盘子，从小到大叠放。目标是将所有盘子从 A 移到 C，每次只能移动一个盘子，且大盘子不能放在小盘子上面。
递归思想
解决这个问题的关键在于将规模为 n 的问题分解为规模更小的子问题。
基本情况
当 n = 1 时，直接将 A 最上面的盘子移到 C 即可终止。
递归分解 若要将 A 上的 n 个盘子移到 C，可以拆解为三步：
- 将 A 上除了最底下的盘子（即上面 n-1 个）移到 B（借助 C 作为辅助）；
- 将 A 最底下的最大盘子移到 C；
- 将 B 上的 n-1 个盘子移到 C（借助 A 作为辅助）。
这样，大问题就被拆成了两个规模为 n-1 的子问题。
算法实现（C++）
class Solution {
public:
void hanota(vector<int>& a, vector<int>& b, vector<int>& c) {
dfs(a, b, c, a.size());
}
private:
void dfs(vector<int>& a, vector<int>& b, vector<int>& c, int n) {
if (n == 1) {
c.push_back(a.back());
a.pop_back();
return;
}
// 将 n-1 个盘子从 A 移到 B
dfs(a, c, b, n - 1);
// 将最大的盘子从 A 移到 C
c.push_back(a.back());
a.pop_back();
// 将 n-1 个盘子从 B 移到 C
dfs(b, a, c, n - 1);
}
};
提示：如果是笔试中遇到这种纯逻辑题，有时可以直接赋值
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;
}
};
以上五个题目涵盖了递归在数学问题、数据结构操作及优化算法中的典型应用。掌握这些模式后，面对类似的递归结构题会有更清晰的思路。