【递归、搜索与回溯】专题一：递归（二）

📝前言说明：

• 本专栏主要记录本人递归，搜索与回溯算法的学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

你可以点击下方链接，进行该专题内不同子专题的学习

点击链接	开始学习
导论	递归 (一) 、递归 (二)
二叉树的深搜	穷举 vs 暴搜 vs 深搜
回溯 vs 剪枝	综合练习
FloodFill算法	记忆化搜索

---

206. 反转链表

题目链接：https://leetcode.cn/problems/reverse-linked-list/description/

个人解

思路：

• 子问题：给一个链表头结点，逆序之后，返回逆序后的头结点
• 函数体：先反转当前节点之后的链表，然后再把当前节点连接在链表的后面
• 递归出口：当当前没有节点或者只剩一个节点

屎山代码：

class Solution {
public:ListNode* reverseList(ListNode* head) {if(head == nullptr || head->next == nullptr) return head;ListNode* newnode = reverseList(head -> next);head->next->next = head; // head->next 就是反转后链表的末尾，让末尾指向headhead->next = nullptr;return newnode;}
};

这道题，也可以改成循环，用双指针解决。

---

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

题目链接：https://leetcode.cn/problems/swap-nodes-in-pairs/description/

个人解

思路：

• 子问题：给你一个头结点，帮我将头结点对应链表的节点两两交换（子问题其实是先通过分析问题后得出来的），然后返回交换后的头结点
• 函数体：将head和head->next交换，然后链接函数的返回结果（后面链表交换好的结果）
• 递归出口：当只有 0 / 1个节点

屎山代码：

class Solution {
public:ListNode* swapPairs(ListNode* head) {if(head == nullptr || head->next == nullptr) return head;ListNode* head2 = head->next;head -> next = swapPairs(head2->next);head2 -> next = head;return head2;}
};

---

50. Pow(x, n)

题目链接：https://leetcode.cn/problems/powx-n/description/

个人解

思路：

• 子问题：
  • n > 0 ：x * x的 n - 1次幂
  • n < 0 ：x 的 n + 1 次幂 / x
• 函数体：x * pow(x, n - 1) 或者 pow(x, n + 1) / x
• 返回值：当 n == 0 return 1

用时：3:00
屎山代码（没通过）：

class Solution {
public:double myPow(double x, int n) {if(n == 0) return 1.0;else if(n > 0)return x * myPow(x, n - 1);elsereturn myPow(x, n + 1) / x;}
};

时间复杂度：O (n)
空间复杂度：O(n)

---

优质解

思路：

快速幂：

• 子问题：求出 x 的 n 次⽅是多少，然后返回
• 先求出 x 的 n / 2 次方是多少，然后根据 n 的奇偶，得出 x 的 n 次方是多少
• 当 n 为 0 的时候，返回 1
• 还要注意，负数可能会溢出

代码：

class Solution
{
public:double myPow(double x, int n) {// x 的 -n 次幂，就是 1 / x 的 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;}
};

时间复杂度：O(log n)
空间复杂度：O(log n)

---

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！