题解 | #从单向链表中删除指定值的节点#

#include <iostream>

using namespace std;
struct ListNode{
    int val;
    ListNode* next;
    ListNode(int val):val(val),next(nullptr){}
};
//从index插入节点的函数,再val1后面插入val2的值
ListNode* AddIndex(ListNode * dummyHead,int val1,int val2)
{
    ListNode* cur=dummyHead;
    while(cur!=nullptr&&cur->val!=val1){
        cur=cur->next;
    }
    ListNode* newNode=new ListNode(val2);
    newNode->next=cur->next;
    cur->next=newNode;
    return dummyHead;
}
//删除指定val值的节点
ListNode* DeleteIndex(ListNode* dummyHead,int val1){
    ListNode* cur=dummyHead;
    while(cur!=nullptr&&cur->next!=nullptr&&cur->next->val!=val1){
        cur=cur->next;
    }
    ListNode*tmp=cur->next;
    cur->next=cur->next->next;
    delete tmp;
    tmp=nullptr;
    return dummyHead;
}
//打印当前链表
void PrintList(ListNode* dummyHead){
    ListNode* cur=dummyHead->next;
    while(cur!=nullptr){
        cout<<cur->val<<" ";
        cur=cur->next;
    }
    cout<<endl;
}
int main() {
    int n;
    int val0;
    cin>>n>>val0;
    ListNode* dummyHead=new ListNode(0);
    ListNode* head=new ListNode(val0);
    dummyHead->next=head;
    ListNode* cur=dummyHead;
    while(n-1){//因为head在外面赋值了，接下来循环里要赋值的就是n-1个节点
        int val2,val1;
        cin>>val1>>val2;//在val2的后面插入Val1
        AddIndex(dummyHead,val2,val1);
        //PrintList(dummyHead);
        n--;
    }
    int val3;//删除的值
    cin>>val3;
    DeleteIndex(dummyHead, val3);
    PrintList(dummyHead);




}

注意这道题中的插入数据是在给出的值之后插数据，所以指针遍历链表的时候，可以用当前指针遍历，不需要cur->next遍历。找到要在【其后面】插入节点的那个数字后（比如数组是2，3，是要在val=3的节点后插入2，先遍历链表找这个3在哪里），cur停在val对应的节点上，直接在cur->next的位置放新的节点即可。有些题目的插入是找到val值后在他的【前面】插入一个节点，那此时就需要用cur->next遍历，找到cur->next=val的节点后，cur停在val前一个节点处，才能正确插入。所以遍历的时候要仔细看题目是哪一种插入。

delete就没什么可说的，一定是cur停在val的前一个节点处，让自己的cur->next=cur->next->next，所以一定得是用cur->next来遍历。注意删除之后，C++中需要删除不需要的节点的内存，并将指针赋为空值以免造成野指针