题目的主要信息：

输入一个单向链表和一个节点的值，其中链表的值不重复。
我们需要从单向链表中删除等于该值的节点，删除后如果链表中无节点则返回空指针。

方法一：

我们用链表结构来模拟整个过程，val表示节点的值，next指向下一个节点。

1、建立链表：首先建立头节点，然后从输入中建立要插入的节点NewNode，遍历一遍已创建的链表，找到值为pre的节点，将NewNode插在后面。

2、删除指定值的节点：遍历一遍链表找到值为n的节点即为要删除的节点。

3、输出链表 alt 具体做法：

#include<iostream>
using namespace std;

struct node{//节点结构
    int val;
    struct node* next;
};

int main(){
    int num,val;
    int next,pre;
    cin>>num>>val;//节点个数
    node* head = new node();
    head->val = val;//创建头节点
    head->next = NULL;
    num--;
    //逐个插入
    while(num--){
        cin>>next>>pre;//next要插到值为pre的后面
        node* newNode = new node();//创建要插入的节点
        newNode->val = next;
        newNode->next = NULL;
        //查找值为pre的节点
        node *p=head;
        while(p){
            if(p->val == pre){
                break;
            }
            else{
                p = p->next;
            }
        }
        if(p){//把NewNode节点插到pre的后面
            node* tmp = p->next;
            p->next = newNode;
            newNode->next = tmp;
        }
    }
    int n;
    cin>>n;//输入要删除的节点的值
    node* p = head;
    if(head){
        node* q = head->next;
        while(q){
            if(q->val == n){
                break;
            }else{
                p = p->next;
                q = q->next;
            }
        }
        if(q){
            node* tmp = q->next;
            p->next = tmp;
            delete q;
        }
    }
    p = head;
    while(p){//输出整个链表
        cout<<p->val<<' ';
        p = p->next;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n^{2})$ ，每插入一个节点都需要遍历一遍链表。
空间复杂度： $O (1)$ ，只用了常数空间。

方法二：

用vector容器模拟链表。

1、find函数查找前节点，用insert函数插入节点。

2、erase函数删除节点。

具体做法：

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int main(){
    int n, val;//n为节点个数
    while(cin>>n>>val){
        vector<int> list;//用vector模拟链表
        list.push_back(val);//头节点
        for(int i=0;i<n-1;i++){
            int next,pre;
            cin>>next>>pre;
            vector<int>::iterator iter = find(list.begin(),list.end(),pre);//next插到pre的后面
            if(iter!=list.end()){
                list.insert(iter+1,next); 
            }else{//如果pre节点在最后，则直接push_back
                list.push_back(next);
            }
        }
        int num;
        cin>>num;//输入要删除的值
        list.erase(find(list.begin(),list.end(),num));
        for(auto i: list){//输出整个链表
            cout << i << " ";
        }
        cout << endl;
    } 
    return 0;
}

复杂度分析：

时间复杂度： $O (n^{2})$ ，每插入一个节点都需要用时间复杂度为 $O (n)$ 的find函数查找pre的位置。
空间复杂度： $O (n)$ ，list的长度为n。

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

题目的主要信息：

方法一：

方法二：