203、移除鏈表元素
·虛擬頭節點
題目鏈接：https://leetcode.cn/problems/remove-linked-list-elements/
思路：鏈表遍歷
???| c->next!=NULL
???洗掉節點
???| c->next=c->next->next;
???c++手動釋放記憶體
代碼實作：
?????時間復雜度O(n);
?????空間復雜度O(1);
/**
* 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* removeElements(ListNode* head, int val) {
ListNode* k=new ListNode(0,head);
ListNode* c=k;
while(c->next!=NULL){
if(c->next->val==val){
ListNode* d=c->next;
c->next=c->next->next;//洗掉節點
delete d;//釋放記憶體
}
else{
c=c->next;
}
}
head = k->next;
delete k;
return head;
}
};
識訓摘要：鏈表題比較生疏，很少考慮手動釋放記憶體（）
學習的文章鏈接：https://programmercarl.com/0203.移除鏈表元素.html#其他語言版本
學習的視頻鏈接：https://www.bilibili.com/video/BV18B4y1s7R9/?spm_id_from=333.788&vd_source=c2b246a405f861a2b3c13ab2b1b1eea6
707、設計鏈表
·就是這題，一下子給我干沉默了orz
題目鏈接：https://leetcode.cn/problems/design-linked-list/
感悟：越是難啃的題目，感覺識訓越多（確信）
???模擬演算的程序真痛苦（淚）
???可以拆成五個小題，它合在一起了
思路：思考鏈表插入位置，先尋找，然后賦值（順序是關鍵）
代碼實作：
class MyLinkedList {
public:
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) {}
};
MyLinkedList() {//初始化
_size=0;
head = new ListNode(0);
}
//尋找第index個節點的值
int get(int index) {//index節點的資料域，index從0開始算
if(index<0||index>_size-1)return -1;
ListNode* cur=head->next;
while(index>0){
cur=cur->next;
index--;
}
return cur->val;
}
//在鏈表頭前面插入val
void addAtHead(int val) {//在鏈表頭前插入一個節點，成為新的頭節點
ListNode* cur=new ListNode(val,head->next);//虛擬頭指向的頭節點，鏈表長度為0時則指向空指標
head->next=cur;
_size++;
}
//在鏈表尾后插入一個節點
void addAtTail(int val) {
ListNode* cur=head;
while(cur->next!=nullptr){//找到鏈表尾
cur=cur->next;
}
cur->next=new ListNode(val);//在鏈表末尾加上
_size++;
}
//index長于鏈表長度時不插入（我直接根據題目描述寫了，也可以只分成兩種情況）
void addAtIndex(int index, int val) {
if(index==_size){//在鏈表尾后加節點
addAtTail(val);
}
else if(index<=0){//在鏈表頭前加節點
addAtHead(val);
}
else if(index<_size){//在鏈表中間加節點
ListNode* cur=head;
ListNode* add=new ListNode(val);
while(index>0){
cur=cur->next;
index--;
}
add->next=cur->next;
cur->next=add;
_size++;
}
}
void deleteAtIndex(int index) {//洗掉index節點
if(index>=0&&index<_size){
ListNode* cur=head;
while(index>0){
cur=cur->next;
index--;
}
ListNode* d=cur->next;
cur->next=d->next;
delete d;//釋放記憶體
_size--;//注意長度減小
}
}
private:
int _size;
ListNode* head;//虛擬頭節點，指向頭節點
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/
識訓摘要：反復看視頻，結合影像能對鏈表的查找、插入有更加清晰的認知，多加練習，還不夠熟練，
學習的文章鏈接：https://programmercarl.com/0707.設計鏈表.html#代碼
學習的視頻鏈接：https://www.bilibili.com/video/BV1FU4y1X7WD/?spm_id_from=333.788&vd_source=c2b246a405f861a2b3c13ab2b1b1eea6
206、反轉鏈表
·賦值的順序是關鍵
我在死回圈里迷了路……
題目鏈接：https://leetcode.cn/problems/reverse-linked-list/submissions/
思路：鏈表通過指標串聯--線性結構
???鏈表在記憶體中不連續分布
???改變指標域改變鏈表方向
???有雙指標法和遞回法兩種
代碼實作：（雙指標）
?????時間復雜度O(n)
?????空間復雜度O(1)
/**
* 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) {
ListNode* cur=head;
ListNode* pre=NULL;//直接是空指標
while(cur!=nullptr){//注意回圈邊界
ListNode* k=cur->next;
cur->next=pre;//反轉
pre=cur;//pre前進
cur=k;//cur前進,因為前面進行了反轉，所以不能=pre，cur應該是k->next
}
return pre;//最后pre在鏈表尾，cur是nullptr,
}
};
識訓摘要：雙指標+中間指標，三個指標就像星星在腦袋上旋轉doge，有空再試試遞回法（遞回苦手）
學習的文章鏈接：https://programmercarl.com/0206.翻轉鏈表.html#雙指標法
學習的視頻鏈接：https://www.bilibili.com/video/BV1nB4y1i7eL/?spm_id_from=333.788&vd_source=c2b246a405f861a2b3c13ab2b1b1eea6
學習時長：7h（orz)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/522951.html
標籤：其他
上一篇：web安全學習(sql注入1)
下一篇：如何讓我的頁面覆寫整個寬度