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

一.题目描述

首先这个题目意思理解起来真的很离谱！！感觉表达的很是不清楚(也可能是我理解能力差吧)，仔细看题目，我们可以知道题目会给出一个单链表和一个值，删除其中节点值等于该值的节点。其输入格式是先输入节点的个数n，然后输入头节点的值head，然后输入n-1个2个数a和b，其中a表示要插入的数，b表示a这个数字插入在值等于b的节点前面。

二.算法一(数组模拟)

根据题目意思我们可以利用数组进行模拟，对于单链表的建立我们用一个数组来维护，我们每一次找到值为b的节点，然后插入，下面是完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int num[N];
int cnt,n,head;
int find(int x){//找到值为x的节点下标
    for(int i=1;i<=cnt;i++){
        if(num[i]==x){
            return i;
        }
    }
    return -1;
}
void add(int cn,int ans){//找到值为ans的节点在其前面插入
    int l=find(ans);
    cnt++;//由于插入一个数计数器加一
    for(int i=cnt;i>=l+1;i--){//从后往前每一个数往后移一位
        num[i]=num[i-1];
    }
    num[l]=cn;
}
int main(){
    cin>>n>>head;
    cnt++;//计数器
    num[cnt]=head;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);//插入
    }
    int p;
    cin>>p;
    for(int i=cnt;i>=1;i--){
        if(num[i]==p) continue;//对于要删除的节点直接不输出
        cout<<num[i]<<" ";
    }
    return 0;
}

时间复杂度：$O(n^2)O(n^2)$ 对于每次操作都要遍历两遍数组，查找要遍历一遍，插入也要遍历一遍。

空间复杂度：$O(n)O(n)$ 需要利用数组来存储链表。

三.算法二(指针)

我们可以利用数组模拟，同时也可以使用链表来模拟。相比于数组模拟，指针模拟更容易进行插入操作。

下面是完整代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int data;
    struct node* next=NULL;
};
int n,head;
node *List;
node* find(int ans){//查找值为ans的节点，注意返回为节点
    node* t=List;
    while(t->data!=ans){
        t=t->next;
    }
    return t;
}
int main(){
    cin>>n>>head;
    List=new node;
    List->data=head;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        node* now=new node;
        now->data=a;
        node* id=find(b);//找到值为b的节点
        //插入
        now->next=id->next;
        id->next=now;
    }
    int ans;
    cin>>ans;
    while(List!=NULL){
        //要删除的节点直接不输出
        if(List->data!=ans){
            cout<<List->data<<" ";
        }
        List=List->next;
    }
    cout<<endl;
    return 0;
}

时间复杂度：$O(n^2)O(n^2)$ 对于每次操作都要遍历一遍遍数组，只是查找要遍历一遍，插入不需要，插入的时间复杂度只有$O(1)O(1)$。

空间复杂度：$O(n)O(n)$ 需要存储链表。