《算法题讲解指南：递归，搜索与回溯算法--递归》--3.反转链表，4.两两交换链表中的节点，5.快速幂

🔥小叶-duck：个人主页

❄️个人专栏：《Data-Structure-Learning》

《C++入门到进阶&自我学习过程记录》

《算法题讲解指南》–优选算法

《算法题讲解指南》–递归、搜索与回溯算法

✨未择之路，不须回头 已择之路，纵是荆棘遍野，亦作花海遨游

目录

3.反转链表

题目链接：

题目描述：

题目示例：

解法(递归)：

算法思路：

C++算法代码：

算法总结及流程解析：

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

题目链接：

题目描述：

题目示例：

解法(递归)：

算法思路：

C++算法代码：

算法总结及流程解析：

5.快速幂

题目链接：

题目描述：

题目示例：

解法(递归-快速幂)：

算法思路：

C++算法代码：

算法总结及流程解析：

结束语

3.反转链表

题目链接：

206. 反转链表 – 力扣（LeetCode）

题目描述：

题目示例：

解法(递归)：

算法思路：

      1.递归函数的含义：交给你一个链表的头指针，你帮我逆序之后，返回逆序后的头结点；       2.函数体：先把当前结点之后的链表逆序，逆序完之后，把当前结点添加到逆序后的链表后面即可；       3.递归出口：当前结点为空或者当前只有一个结点的时候，不用逆序，直接返回。       注意注意注意：链表的题一定要画图，搞清楚指针的操作！

C++算法代码：

/**
* 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相当于是反转后的尾结点
head->next = nullptr;
return newhead;
}
};

算法总结及流程解析：

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

题目链接：

24. 两两交换链表中的节点 – 力扣（LeetCode）

题目描述：

题目示例：

解法(递归)：

算法思路：

      1.递归函数的含义：交给你一个链表，将这个链表两两交换一下，然后返回交换后的头结点；       2.函数体：先去处理一下第二个结点往后的链表，然后再把当前的两个结点交换一下，连接上后面处理后的链表；       3.递归出口：当前结点为空或者当前只有一个结点的时候，不用交换，直接返回。       注意注意注意：链表的题一定要画图，搞清楚指针的操作！

这道题其实在我们的优选算法中已经讲解过了，只是当时是利用其链表的性质使用循环、迭代(模拟算法)来解决的，感兴趣的可以去看看。

《算法题讲解指南：优选算法-链表》–51.两数相加，52.两两交换链表中的节点-CSDN博客

但是我相信如果真的理解了用宏观的视角来看待递归，一定会觉得递归比上面的模拟实现简单太多了。

C++算法代码：

/**
* 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* tmp = swapPairs(head->next->next);
ListNode* newhead = head->next;
newhead->next = head;
head->next = tmp;
return newhead;
}
};

算法总结及流程解析：

5.快速幂

题目链接：

50. Pow(x, n) – 力扣（LeetCode）

题目描述：

题目示例：

解法(递归-快速幂)：

算法思路：

      1.递归函数的含义：求出 x 的 n 次方是多少，然后返回；       2.函数体：先求出 x 的 n/2 次方是多少，然后根据 n 的奇偶，得出 x 的 n 次方是多少；       3.递归出口：当 n 为 0 的时候，返回 1 即可。

C++算法代码：

class Solution {
public:
double Pow(double x, long long n)
//因为n为负数时可以取到-2^32,当转成-n时则超出int最大值，需要改成long long类型
{
if(n == 0)
{
return 1;
}
double tmp = myPow(x, n / 2);
return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
}

double myPow(double x, int n)
{
double ret = n < 0 ? Pow(x, -(long long)n) : Pow(x, n);
if(n < 0)
{
ret = 1 / ret;
}
return ret;
}
};

算法总结及流程解析：

结束语

      到此，3.反转链表，4.两两交换链表中的节点，5.快速幂 这三道算法题就讲解完了。反转链表：通过递归逆序后续链表，再将当前节点接在尾部；两两交换链表节点：递归处理后续链表后交换当前两个节点；快速幂：利用分治思想递归计算x的n次方。希望大家能有所收获！