203.移除链表元素
文章链接：https://programmercarl.com/0203.移除链表元素.html#算法公开课
视频讲解：https://www.bilibili.com/video/BV18B4y1s7R9
题目出处：https://leetcode.cn/problems/remove-linked-list-elements/
卡哥在这里讲解了为什么要使用虚拟头节点，以及使用和不使用的区别，不清楚的话可以看视频讲解
- 方一：直接删除头节点
写的时候有几个小问题需要注意，已经在代码中标出
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {//不使用虚拟头节点，直接删除//删除头节点（头节点特殊，删除方式不一样，直接将head后移一个节点）while(head!=NULL&&head->val==val){ //这里一开始写的时候用的if，但是如果head后面的节点依然符合要求，则会漏掉这种情况ListNode* tmp=head;head=head->next;delete tmp;}//删除非头节点ListNode* cur=head;while(cur!=NULL&&cur->next!=NULL){ //这里一开始写的时候没有写cur!=NULL，这样是不行的，因为如果它为空了再操作会导致空指针错误if(cur->next->val==val){ ListNode* tmp=cur->next;cur->next=cur->next->next;delete tmp;}else{cur=cur->next;}}return head;}
};
- 方二：使用虚拟头节点
错误如下图所示：
这里会报错的原因是 dummyHead 没有被初始化。dummyHead 是一个指向 ListNode 类型的指针，但没有给它分配内存空间。当前代码只声明了一个指针，但它指向的是未定义的内存区域，因此在访问 dummyHead->next 时会导致未定义行为或崩溃。
所以这里应该写成：
ListNode* dummyHead = new ListNode(0); //
dummyHead->next = head;
总的代码如下所示：
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {//使用虚拟头节点ListNode* dummyHead=new ListNode(0); //注意将指针初始化dummyHead->next=head;ListNode* cur=dummyHead;while(cur->next!=NULL){if(cur->next->val==val){ListNode* tmp=cur->next;cur->next=cur->next->next;delete tmp;}else{cur=cur->next;}}head=dummyHead->next;return head;}
};
- 方三：使用递归也很有意思
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {//使用递归if(head==nullptr){return nullptr;}if(head->val==val){ListNode* newHead=removeElements(head->next,val);delete head;return newHead;}else{head->next=removeElements(head->next,val); //这里一开始没有想到head->nextreturn head;}}
};
707.设计链表
文章链接：https://programmercarl.com/0707.设计链表.html
视频链接：https://www.bilibili.com/video/BV1FU4y1X7WD
题目链接：https://leetcode.cn/problems/design-linked-list/description/
先构造节点，并为类写构造函数进行初始化。
class MyLinkedList {
public://定义节点struct LinkNode{int val;LinkNode* next;LinkNode():next(nullptr){}//构造函数LinkNode(int val):val(val),next(nullptr){}//重载构造函数};MyLinkedList() { //构造函数dummyHead=new LinkNode();size=0;}
private:int size;LinkNode* dummyHead;
};
以下为学校内学到的写法：
- 头插法：
void addAtHead(int val) {LinkNode* s=new LinkNode(val);s->next=dummyHead->next;dummyHead->next=s;}
- 尾插法：
void addAtTail(int val) {LinkNode* s=new LinkNode(val);LinkNode* r=dummyHead;while(r->next!=NULL){r=r->next;}r->next=s;size++;}
- 在index之前插入
void addAtIndex(int index, int val) {if(index>size||index<0){return;}LinkNode* cur=dummyHead;while(index--){cur=cur->next;}LinkNode* s=new LinkNode(val);s->next=cur->next;cur->next=s;size++;}
- 获取第index个节点值
int get(int index) {if(index>(size-1)||index<0) return -1;LinkNode* cur=dummyHead->next;while(index--){cur=cur->next;}return cur->val;}
- 删除第index个节点
void deleteAtIndex(int index) {if(index<0||index>=size) return;LinkNode* cur=dummyHead;while(index--){cur=cur->next;}LinkNode* tmp= cur->next;cur->next=cur->next->next;delete tmp;tmp=nullptr;//这里最好将其赋为空指针//delete命令指示释放了tmp指针原本所指的那部分内存，//被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，//如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针//如果之后的程序不小心使用了tmp，会指向难以预想的内存空间size--;}
206.反转链表
- 双指针的写法：
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* cur=head;ListNode* pre=nullptr;while(cur!=NULL){ListNode* tmp=cur->next;cur->next=pre;pre=cur;cur=tmp;}return pre;}
};
- 递归写法：
class Solution {
public:ListNode* reverse(ListNode* pre,ListNode*cur){// if(cur!=NULL){// ListNode* tmp=cur->next;// cur->next=pre;// reverse(cur,tmp);// }// else return pre;if(cur==NULL) return pre;ListNode* tmp=cur->next;cur->next=pre;return reverse(cur,tmp);}ListNode* reverseList(ListNode* head) {ListNode* pre=nullptr;ListNode* cur=head;return reverse(pre,cur);}
};
第一次写，写成了注释掉的那部分，说明对递归还不太熟
