📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：练题
🎯长路漫漫浩浩，万事皆有期待
移除链表元素
链表问题大多都可以用虚拟头结点的方法，使链表的插入和删除操作变得简单。
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，只是遍历取点就可以不用加
设计链表
设计链表是一道综合题，涵盖了很多有关于链表的函数接口，适合练习，整体思路不算很难。
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的话那就会和在最后一个元素前插入冲突了
反转链表
思路明确的同时还要注意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->next
cur->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，所以要看具体情况。
总结：
今天的三道题虽然之前做过，但从循环到递归的转变感觉第一次非常清晰的领悟了。接下来，我们继续进行算法练习·。希望我的文章和讲解能对大家的学习提供一些帮助。
当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~
