《算法题讲解指南：递归，搜索与回溯算法--递归》--3.反转链表，4.两两交换链表中的节点，5.快速幂
🔥小叶-duck：个人主页
❄️个人专栏：《Data-Structure-Learning》
✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游
目录
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.两两交换链表中的节点-ZEEKLOG博客
但是我相信如果真的理解了用宏观的视角来看待递归，一定会觉得递归比上面的模拟实现简单太多了。
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次方。希望大家能有所收获！
