【算法练习Day3】移除链表元素设计链表反转链表

在这里插入图片描述

📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：练题
🎯长路漫漫浩浩，万事皆有期待

文章目录

移除链表元素
- 其他问题
设计链表
- 其他问题
反转链表
- 其他问题
总结：

移除链表元素

203. 移除链表元素 - 力扣（LeetCode）

链表问题大多都可以用虚拟头结点的方法，使链表的插入和删除操作变得简单。

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dunnmyhead=new ListNode(0);// 设置一个虚拟头结点dunnmyhead->next=head;// 将虚拟头结点指向head，这样方面后面做删除操作ListNode* cur=dunnmyhead;while(cur->next!=nullptr){if(cur->next->val==val){ListNode* tmp=cur->next;cur->next=cur->next->next;delete tmp;}else{cur=cur->next;}}head=dunnmyhead->next;delete dunnmyhead;return head;}
};

这道题并不难，值得注意的是，创建一个临时指针，指向head，然后判断它的值是否等于val，要注意的是用cur->next->val来判断值是否是我们需要找的，如果是的话，cur指向的正是要删除节点的上一个节点，直接将cur的next指针连到要删除节点的下一个位置就可以了

其他问题

● 注意：指针问题, 写删除链表题的时候经常少了else判断, 链表首要想好指针是怎么移动的，是否会访问null即可

● 对于链表问题可以多用笔画画图,这样会加深对指针和节点实体的理解,代码的鲁棒性如何通常可以利用边界case尝试，很多都是因为空指针的错误，手动画图走一遍自己的代码一般就能发现。

● 是否要添加虚拟头结点：
虚拟头结点的主要目的是为了避免对头结点的特殊处理；这个处理就指的是修改操作。所以可以这样：涉及到对链表修改(如插入，删除，移动)的，都加个dummy，只是遍历取点就可以不用加

设计链表

707. 设计链表 - 力扣（LeetCode）

设计链表是一道综合题，涵盖了很多有关于链表的函数接口，适合练习，整体思路不算很难。

class MyLinkedList {
public:// 定义链表节点结构体struct Listnode{int val;Listnode* next;Listnode(int val):val(val),next(nullptr){}};// 初始化链表MyLinkedList() {_size=0;_dummyHead=new Listnode(0);// 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点}// 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点int get(int index) {if(index<0||index>(_size-1)){return -1;}Listnode* cur=_dummyHead->next;while(index--) // 如果--index 就会陷入死循环{cur=cur->next;}return cur->val;}// 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点void addAtHead(int val) {Listnode* newnode=new Listnode(val);newnode->next=_dummyHead->next;_dummyHead->next=newnode;_size++;}// 在链表最后面添加一个节点void addAtTail(int val) {Listnode* newnode=new Listnode(val);Listnode*cur=_dummyHead;while(cur->next){cur=cur->next;}cur->next=newnode;_size++;}// 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。// 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点// 如果index大于链表的长度，则返回空// 如果index小于0，则在头部插入节点void addAtIndex(int index, int val) {if(index>_size){return ;}if(index<0){index=0;}Listnode* newnode=new Listnode(val);Listnode* cur=_dummyHead;while(index--){cur=cur->next;}newnode->next=cur->next;cur->next=newnode;_size++;}// 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的void deleteAtIndex(int index) {if(index<0||index>(_size-1)){return ;}Listnode* cur=_dummyHead;while(index--){cur=cur->next;}Listnode* tmp=cur->next;cur->next=cur->next->next;delete tmp;//delete命令指示释放了tmp指针原本所指的那部分内存，//被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，//如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针//如果之后的程序不小心使用了tmp，会指向难以预想的内存空间tmp=nullptr;_size--;        }private:int _size;Listnode* _dummyHead;
};

起初写的时候很懵，还在想为什么没有给头节点指针，而是只有index？后来看题解才知道要自己创建结构体，和虚拟头节点(方便空链表插入)。整体思路难度适中，只是接口多了一些，思路清晰还是能写出得出来的。

其他问题

● 设计链表因为调用了很多函数，一旦出错可能不知道调试从何下手，因此建议把代码放到本地IDE上，一个一个函数去测试看出错在什么地方

● 对于第index个有所混淆，做题目前一定要理解题目的意思，这里的index是从0开始的

● addAtIndex 方法中描述的“如果 index 等于链表的长度，则该节点将附加到链表的末尾” 这句话中链表长度这里是指 size而不是size - 1，如果是size-1的话那就会和在最后一个元素前插入冲突了

反转链表

206. 反转链表 - 力扣（LeetCode）

思路明确的同时还要注意head指针传进来时，若是空的情况要怎么处理，以及应该创建几个临时节点，分别保存什么。

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* tmp=nullptr;// 保存cur的下一个节点ListNode* cur=head;ListNode* pre=nullptr;while(cur){tmp=cur->next; // 保存一下 cur的下一个节点，因为接下来要改变cur->nextcur->next=pre;// 翻转操作pre=cur; // 更新pre 和 cur指针cur=tmp;}return pre;}
};

注意：更新pre 和 cur指针时，先让pre=cur，否则，cur指向的节点就丢失了

创立三个临时指针，一个用来保存要反转的节点的下一个链接节点，一个用来指向下一个反转节点的next连接到哪里，另一个代表当前要反转的节点。缺一不可的，一开始pre要指向null，使第一个反转的链表有指向的指针，只要明确要用到几个指针，以及分别初始化为什么值，这道题就解的出来了。

递归代码实现，和上面的方法思路是相同的。

class Solution {
public:ListNode* reverse(ListNode* pre,ListNode* cur){if(cur==nullptr){return pre;}ListNode* tmp=cur->next;cur->next=pre;// 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步// pre = cur;// cur = temp;return reverse(cur,tmp);}ListNode* reverseList(ListNode* head) {// 和双指针法初始化是一样的逻辑// ListNode* cur = head;// ListNode* pre = NULL;return reverse(nullptr,head);}
};

其他问题

● 链表一定要分清节点和指针的概念。 new ListNode()是真实存在的一个节点, head = new ListNode() 相当于 head指针指向了一个真实的节点, node = head, 相当于node和head同时指向了这个真实的节点

● 尽量不要去动虚拟头节点,因为虚拟头节点本来就是个工具节点,操作后面的节点本身就好

● 为什么有时候需要判定cur->next !=nullptr 有时候又不需要只用判断cur!=nullptr呢？
其实这个要看场景，一般就是看你如果不判断的话会不会导致空指针异常，因为如果你的指针遍历到null还调用它的属性或方法肯定就会报错的，但是有时候的情况不会遍历到cur->next，所以要看具体情况。