递归（典型算法思想）—— OJ例题算法解析思路
目录
一、面试题 08.06. 汉诺塔问题 - 力扣（LeetCode）
算法代码：
代码思路概述
详细代码逻辑解释
类定义:
入口函数:
递归函数:
递归步骤:
总结
二、21. 合并两个有序链表 - 力扣（LeetCode）
方法一：算法代码（链表法）
方法二：算法代码（递归）
代码思路概述
详细代码逻辑解释
链表节点定义:
合并链表函数:
基线条件:
递归步骤:
总结
三、206. 反转链表 - 力扣（LeetCode）
方法一：算法代码（链表法）
方法二：算法代码（递归）
代码思路概述
详细代码逻辑解释
链表节点定义:
反转链表函数:
基线条件:
递归步骤:
总结
四、24. 两两交换链表中的节点 - 力扣（LeetCode）
方法一：算法代码（链表法）
方法二：算法代码（递归）
代码思路概述
详细代码逻辑解释
链表节点定义:
交换链表节点函数:
基线条件:
递归步骤:
总结
五、50. Pow(x, n) - 力扣（LeetCode）
算法代码：
代码思路概述
详细代码逻辑解释
入口函数:
快速幂算法:
递归步骤:
总结
一、面试题 08.06. 汉诺塔问题 - 力扣（LeetCode）
算法代码：
class Solution {
public:void hanota(vector<int>& a, vector<int>& b, vector<int>& c) {dfs(a, b, c, a.size());}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;}dfs(a, c, b, n - 1);c.push_back(a.back());a.pop_back();dfs(b, a, c, n - 1);}
};代码思路概述
-
函数入口:
hanota函数是用户调用的入口，用于启动汉诺塔的解决过程。 -
递归实现: 使用深度优先搜索（DFS）策略，通过递归函数
dfs来实现圆盘的移动。 -
移动规则: 递归地将圆盘从源柱子移动到目标柱子，遵循汉诺塔的移动规则（只能一次移动一个圆盘，且不能将大圆盘放在小圆盘上）。
-
结束条件: 当只剩下一个圆盘时，直接将其移动到目标柱子。
详细代码逻辑解释
-
类定义:
class Solution { public:-
定义一个名为
Solution的类，通常在 LeetCode 等平台上会使用这个类结构来封装解法。
-
-
入口函数:
void hanota(vector<int>& a, vector<int>& b, vector<int>& c) {dfs(a, b, c, a.size()); }-
hanota函数接收三个参数，分别代表三根柱子（a、b、c），其中a是源柱子，b是辅助柱子，c是目标柱子。 -
调用
dfs函数，传入柱子和圆盘的数量n（即a.size()，表示初始圆盘的数量）。
-
-
递归函数:
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;}... }-
dfs函数实现了核心的汉诺塔移动逻辑。 -
基本情况: 如果
n等于 1，表示只剩下一个圆盘，直接将其从源柱子a移动到目标柱子c。这通过push_back将圆盘添加到目标柱子，并使用pop_back从源柱子移除圆盘来实现。
-
-
递归步骤:
dfs(a, c, b, n - 1); c.push_back(a.back()); a.pop_back(); dfs(b, a, c, n - 1);-
第一步: 递归调用
dfs(a, c, b, n - 1)，将n-1个圆盘从源柱子a移到辅助柱子b，使用目标柱子c作为辅助。 -
第二步: 将最大的圆盘（原柱子
a的最后一个元素）移动到目标柱子c。 -
第三步: 递归调用
dfs(b, a, c, n - 1)，将n-1个圆盘从辅助柱子b移到目标柱子c，使用源柱子a作为辅助。
-
总结
-
递归思想: 汉诺塔问题的关键在于用递归分解问题，每次只处理一个圆盘，并通过临时柱子作为辅助，以满足汉诺塔的移动规则。
-
时间复杂度: 汉诺塔问题的时间复杂度为 (O(2^n))，因为每次移动一个圆盘都会导致两个递归调用。
-
空间复杂度: 由于递归调用的栈空间，空间复杂度为 (O(n))。
-
应用场景: 汉诺塔问题是经典的递归示例，常用于教学和算法设计的入门。
通过以上分析，您可以更好地理解这段代码是如何利用递归来解决汉诺塔问题的。
二、21. 合并两个有序链表 - 力扣（LeetCode）
方法一：算法代码（链表法）
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
//[] []
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{//处理链表为空的情况if (list1 == NULL){return list2;}if (list2 == NULL){return list1;}//创建新的链表ListNode* newHead, * newTail;newHead = newTail = (ListNode*)malloc(sizeof(ListNode));//malloc和realloc只有在内存不够的情况下会申请空间失败，所以可不用判断是否申请空间成功，要判断也是可以的//创建两个指针分别指向两个链表的头结点ListNode* l1 = list1;ListNode* l2 = list2;while (l1 && l2){if (l1->val < l2->val){//l1尾插到新链表中newTail->next = l1;newTail = newTail->next;l1 = l1->next;}else{newTail->next = l2;newTail = newTail->next;l2 = l2->next;}}//跳出循环只有两种情况：要么l1为空（l2肯定不为空），要么l2为空（l1不为空）if (l1)newTail->next = l1;if (l2)newTail->next = l2;ListNode* ret = newHead->next;free(newHead);newHead = NULL;return ret;
}方法二：算法代码（递归）
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
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;}}
};代码思路概述
-
链表定义: 通过结构体
ListNode定义链表节点。 -
递归合并: 使用递归函数
mergeTwoLists来合并两个已排序的链表。 -
基线条件: 当遇到其中一个链表为空时，直接返回另一个链表。
-
递归步骤: 比较两个链表的头节点，将较小的节点加入结果链表，并继续合并其余部分。
详细代码逻辑解释
-
链表节点定义:
struct ListNode {int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {} };-
ListNode结构体定义了链表节点，包含一个整数值val和一个指向下一个节点的指针next。 -
提供了多个构造函数，方便创建链表节点。
-
-
合并链表函数:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {-
mergeTwoLists函数接收两个链表的头指针l1和l2，并返回合并后的链表头指针。
-
-
基线条件:
if (l1 == nullptr)return l2; if (l2 == nullptr)return l1;-
如果
l1为空，返回l2，因为此时链表只包含l2的节点。 -
如果
l2为空，返回l1，因为此时链表只包含l1的节点。
-
-
递归步骤:
if (l1->val <= l2->val) {l1->next = mergeTwoLists(l1->next, l2);return l1; } else {l2->next = mergeTwoLists(l1, l2->next);return l2; }-
比较节点值: 首先比较
l1和l2的当前节点值。 -
如果
l1的值小于等于l2的值：-
将
l1的next指向合并后的链表，继续递归合并l1->next和l2。 -
返回
l1作为结果链表的头。
-
-
如果
l2的值小于l1的值：-
将
l2的next指向合并后的链表，继续递归合并l1和l2->next。 -
返回
l2作为结果链表的头。
-
-
总结
-
递归思想: 该算法利用递归方法分治地解决了链表合并问题，确保每次只处理当前节点的合并。
-
时间复杂度: 时间复杂度为 (O(n + m))，其中 (n) 和 (m) 分别是两个链表的长度，因为每个节点都将被访问一次。
-
空间复杂度: 由于递归调用栈的深度与合并后的链表长度成正比，因此空间复杂度为 (O(n + m))。
-
应用场景: 该方法可以应用于需要合并多个已排序数据源的场景，如合并多个排好序的数组或链表。
这段代码展示了如何使用递归技术处理链表，体现了分治思想的优雅与有效。
三、206. 反转链表 - 力扣（LeetCode）
方法一：算法代码（链表法）
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{//处理空链表if (head == NULL){return head;}//创建三个指针ListNode* n1, * n2, * n3;n1 = NULL, n2 = head, n3 = n2->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if(n3)n3 = n3->next;}//此时n1就是链表反转后新的头结点return n1;
}方法二：算法代码（递归）
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
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;}
};代码思路概述
-
链表定义: 通过结构体
ListNode定义链表节点。 -
递归反转: 使用递归函数
reverseList来反转链表。 -
基线条件: 当链表为空或只有一个节点时，直接返回头节点。
-
递归步骤: 递归反转链表的其余部分，并调整指针来完成反转。
详细代码逻辑解释
-
链表节点定义:
struct ListNode {int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {} };-
ListNode结构体定义了链表节点，包含一个整型值val和指向下一个节点的指针next。 -
提供了多个构造函数，以便在创建节点时灵活使用。
-
-
反转链表函数:
ListNode* reverseList(ListNode* head) {-
reverseList函数接收一个指向链表头节点head的指针，并返回反转后的链表头节点。
-
-
基线条件:
if (head == nullptr || head->next == nullptr)return head;-
如果
head为空，或者链表只有一个节点（head->next为空），直接返回head。这是递归的基线条件，意味着我们已经到达了链表的末尾。
-
-
递归步骤:
ListNode* newHead = reverseList(head->next); head->next->next = head; head->next = nullptr; return newHead;-
递归调用: 调用
reverseList(head->next)，递归地反转链表的其余部分，返回新链表的头节点newHead。 -
调整指针:
-
head->next->next = head;将当前节点head的指针设置为指向自己，这样就反转了当前节点与下一个节点之间的链接。 -
head->next = nullptr;将当前节点的next指针设为nullptr，这标志着新链表的末尾。
-
-
返回新头: 返回
newHead作为反转后的链表的头节点。
-
总结
-
递归思想: 该算法利用递归的方式，将问题逐步分解，直到达到基本情况，然后在回溯过程中调整指针实现链表的反转。
-
时间复杂度: 时间复杂度为 (O(n))，其中 (n) 是链表的长度，因为每个节点都会被访问一次。
-
空间复杂度: 由于递归调用栈的深度与链表长度成正比，因此空间复杂度为 (O(n))，在最坏情况下，这将是最大递归深度。
四、24. 两两交换链表中的节点 - 力扣（LeetCode）
方法一：算法代码（链表法）
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* swapPairs(ListNode* head) {if (head == nullptr || head->next == nullptr)return head;ListNode* newHead = new ListNode(0);newHead->next = head;ListNode *prev = newHead, *cur = prev->next, *next = cur->next,*nnext = next->next;while (cur && next) {// 交换结点prev->next = next;next->next = cur;cur->next = nnext;// 修改指针prev = cur; // 注意顺序cur = nnext;if (cur)next = cur->next;if (next)nnext = next->next;}cur = newHead->next;delete newHead;return cur;}
};方法二：算法代码（递归）
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
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;}
};代码思路概述
-
链表定义: 通过结构体
ListNode定义链表节点。 -
递归交换: 使用递归函数
swapPairs来交换链表中的相邻节点。 -
基线条件: 当链表为空或只有一个节点时，直接返回头节点。
-
递归步骤: 交换当前节点和下一个节点，并递归处理其余部分。
详细代码逻辑解释
-
链表节点定义:
struct ListNode {int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {} };-
ListNode结构体定义了链表节点，包含一个整型值val和指向下一个节点的指针next。 -
提供了多个构造函数，以便在创建节点时灵活使用。
-
-
交换链表节点函数:
ListNode* swapPairs(ListNode* head) {-
swapPairs函数接收一个指向链表头节点head的指针，并返回交换后的链表头节点。
-
-
基线条件:
if (head == nullptr || head->next == nullptr)return head;-
如果
head为空，或者链表只有一个节点（即head->next为空），直接返回head。这是递归的基线条件，意味着我们已经无法再进行交换。
-
-
递归步骤:
auto tmp = swapPairs(head->next->next); auto ret = head->next; head->next->next = head; head->next = tmp; return ret;-
递归调用: 调用
swapPairs(head->next->next)，递归地处理从第三个节点开始的链表，返回的结果链表为tmp。这将为后续的交换提供剩余的部分。 -
交换节点:
-
auto ret = head->next;记录下当前节点的下一个节点head->next，该节点将在交换后成为新的头节点。 -
head->next->next = head;将当前节点head指向其后面的节点（即head->next），完成交换。 -
head->next = tmp;将当前节点的next指向处理后的剩余链表。
-
-
返回新头: 返回
ret，即交换后的新头节点。
-
总结
-
递归思想: 该算法利用递归的方式将链表逐步分解，每次交换两个相邻节点，并在回溯过程中重新组织指针，实现了链表节点的交换。
-
时间复杂度: 时间复杂度为 (O(n))，其中 (n) 是链表的长度，因为每个节点都会被访问一次。
-
空间复杂度: 由于递归调用栈的深度与链表长度成正比，因此空间复杂度为 (O(n))，在最坏情况下，这将是最大递归深度。
-
应用场景: 此方法可用于需要在链表中进行相邻元素交换的场景，如交换操作、链表重排等。
这段代码展示了如何用递归有效地处理链表操作，展现了指针操作的灵活性和递归思想的优雅。
五、50. Pow(x, n) - 力扣（LeetCode）
算法代码：
class Solution {
public:double myPow(double x, int 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;}
};代码思路概述
-
入口函数:
myPow是用户调用的入口，处理负指数的情况。 -
快速幂算法: 使用
pow函数实现快速幂计算。 -
基线条件: 处理幂为零的特殊情况。
-
递归步骤: 通过分治法快速减少问题规模，从而高效计算结果。
详细代码逻辑解释
-
入口函数:
double myPow(double x, int n) {return n < 0 ? 1.0 / pow(x, -(long long)n) : pow(x, n); }-
myPow函数接收一个基数x和一个指数n。 -
如果
n为负，则调用pow(x, -(long long)n)，并返回其倒数 (1.0 / ext{pow}(x, -n))。 -
否则，直接调用
pow(x, n)计算 (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; }-
pow函数实现了快速幂的计算，接收基数x和非负的长整型指数n。 -
基线条件: 当
n等于 0 时，返回 (1.0)，因为任何数的零次方都是 1。
-
-
递归步骤:
double tmp = pow(x, n / 2); return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;-
通过递归调用
pow(x, n / 2)计算 (x^{n/2}) 并将结果存储在tmp变量中。 -
偶次方: 如果
n是偶数，返回 (tmp imes tmp)，即 ((x{n/2})2)。 -
奇次方: 如果
n是奇数，返回 (tmp imes tmp imes x)，即 ((x{n/2})2 imes x)。
-
总结
-
快速幂算法: 该算法的核心在于通过递归和分治的策略，将问题规模减半，从而有效地减少计算次数。时间复杂度为 (O(\log n))，比直接计算 (x^n) 的 (O(n)) 效率高得多。
-
时间复杂度: 整个算法的时间复杂度为 (O(\log n))，因为每次递归调用会将
n减半。 -
空间复杂度: 由于递归调用栈的深度与指数
n成正比，空间复杂度为 (O(\log n))。 -
应用场景: 该方法非常适用于需要计算浮点数的幂的场景，比如在科学计算、金融模型等领域。
这段代码展示了如何高效地计算幂，通过有效的递归策略，体现了算法优化的思维方式。