排序算法，手撕快排，二分查找要整理刷一遍
206. 反转链表
双指针法
自己的写的，用tmp保存下一个开始的节点；先移动慢指针，再移动快指针。
/**
* 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* front=head->next;
ListNode* behind=head;
ListNode* tmp=front->next;
front->next=behind;
behind->next=nullptr; //第一个翻转后尾指针是nullptr
behind=front;
front=tmp;
while(front!=nullptr){
tmp=front->next;
front->next=behind;
behind=front;
front=tmp;
}
return behind; //返回尾指针，因为while条件是front指向null，所以头指针是behind
}
};
从头结点开始，慢指针从null开始，这样就不用重复写了。
/**
* 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* front=head;
ListNode* behind=nullptr;
ListNode* tmp;
while(front!=nullptr){
tmp=front->next;
front->next=behind;
behind=front;
front=tmp;
}
return behind; //返回尾指针，因为while条件是front指向null，所以头指针是behind
}
};
递归法
自己的思路：
递归法：
-
终止条件
-
重复的部分（原子操作）--只针对两个节点的情况，剩下的都翻转好了
没写好的
/**
* 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* front=head;
// ListNode* behind=nullptr;
// ListNode* front;
// ListNode* behind;
ListNode* tmp=front->next;
front->next=behind;
behind=front;
front=reverseList(head->next);
return front;
}
};
修改后的
/**
* 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;
}
};
环形链表
快慢指针，数学计算
思路：
-
判断是否有环？
-
终止条件：无环时遍历完链表
while(fast!=nullptr && fast->next!=nullptr)
-
-
若有环，则计算入口。
-
x=z，当多走一圈时 -
(x+y)*2 = x+y+(y+z)*n,n=1时，x=z
-
实现：
-
快指针一次走两步，慢指针一次走一步。快指针一定先进入环。
-
计算环入口
/**标签：head,ListNode,val,nullptr,Day2,next,链表,front From： https://www.cnblogs.com/good-mind/p/18117849
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast=head;
ListNode* slow=head;
while(fast!=nullptr && fast->next!=nullptr){ //遍历完链表结束
fast=fast->next->next; //因为一次走两步，所以要提前检查fast->next是否为空指针，否则报错
slow=slow->next; //slow一次走一步
if(fast==slow){ //从相遇的地方开始，记录fast slow相遇的地方
ListNode* x=head;
ListNode* z=fast;
while(x!=z){
x=x->next;
z=z->next;
}
return x; //相遇的地方是入口点
}
}
return NULL;
}
};