一.汉诺塔
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/41ef801f08ac46a79f506bfca2b3cf8d.png)
汉诺塔
1.思路一:
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/3fc2e82077f64636a4a0b68447447b43.png)
class Solution {
public:
void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
int n = A.size();
def(A,B,C,n);
}
void def(vector<int>& A, vector<int>& B, vector<int>& C, int n)
{
if(n==1)
{
C.push_back(A.back());
A.pop_back();
return;
}
def(A,C,B,n-1);
C.push_back(A.back());
A.pop_back();
def(B,A,C,n-1);
}
};
2.GIF题目解析
二.合并两个有序链表
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/9a0d2a52b9904d3ba56fc52dc939b446.png)
合并两个有序链表
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/390ff087432047a6a93df39818a1f90d.png)
1.思路一:
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_2_1 {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == nullptr)
return list2;
if (list2 == nullptr)
return list1;
ListNode* head = new ListNode();
ListNode* cur = head;
recursion(list1, list2, cur);
return head->next;
}
void recursion(ListNode*& list1, ListNode*& list2, ListNode*& cur)
{
if (list1 == nullptr || list2 == nullptr)
{
if (list1 == nullptr && list2 != nullptr)
cur->next = list2;
else if (list1 != nullptr && list2 == nullptr)
cur->next = list1;
return;
}
int val1 = list1->val;
int val2 = list2->val;
if (val1 >= val2)
{
cur->next = list2;
cur = cur->next;
ListNode* next2 = cur->next;
cur->next = nullptr;
recursion(list1, next2, cur);
}
else
{
cur->next = list1;
cur = cur->next;
ListNode* next1 = cur->next;
cur->next = nullptr;
recursion(next1, list2, cur);
}
}
};
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == nullptr)
return list2;
if (list2 == nullptr)
return list1;
int val1 = list1->val;
int val2 = list2->val;
if (val1 >= val2)
{
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
else
{
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
return nullptr;
}
};
2.GIF题目解析
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/e43c55763d5246328c3b8e4b83fa6c1a.gif)
三.反转链表
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/c5e6c314b1334d22bfe4d449381711f4.png)
反转链表
1.思路一:
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/88b7d43904a74f76b6d03d3952e9415c.png)
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_3 {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr)
return nullptr;
ListNode* newhead = nullptr;
dfs(head, newhead);
return newhead;
}
ListNode*& dfs(ListNode*& head, ListNode*& rehead)
{
if (head->next == nullptr)
{
rehead = head;
return head;
}
ListNode* prev = dfs(head->next, rehead);
prev->next = head;
head->next = nullptr;
return head;
}
};
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;
}
};
2.GIF题目解析
![请添加图片描述](https://img-blog.csdnimg.cn/direct/0da155aa711f4872a571963fda52531c.gif)
四.两两交换链表中的节点
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/e97501172de248df9bc404c1c3ebb319.png)
两两交换链表中的节点
1.思路一:
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/58d192e8bcca4121b478719f29110286.png)
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(head==nullptr)
return nullptr;
if(head->next == nullptr)
return head;
ListNode* newnext_r = head->next->next;
ListNode* newnext_l = head->next;
head->next->next = head;
head->next = swapPairs(newnext_r);
return newnext_l;
}
};
2.GIF题目解析
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/3810332279d943bab5ffdd938c0772b4.gif)
五.pow(X,N)-快速幂
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/34dfbd870d9f47f0b471ec2a5018fbf6.png)
pow(X,N)-快速幂
1.思路一:快速幂递归
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/c30c418da26243cd85b3c7a81f3e9330.png)
class Solution_5 {
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;
double tmp = pow(x, n / 2);
return (n % 2 == 0 ? tmp * tmp : tmp * tmp * x);
}
};