华为机试-从单向链表中删除指定值的节点（中等）

题目描述

输入一个单向链表和一个节点的值，从单向链表中删除等于该值的节点，删除后如果链表中无节点则返回空指针。
6 2 1 2 3 2 5 1 4 5 7 2 2
则第一个参数6表示输入总共6个节点，第二个参数2表示头节点值为2，剩下的2个一组表示第2个节点值后面插入第1个节点值，为以下表示:
1 2 表示为
2->1
链表为2->1

方法1：

用c++的stl库，其中用vector也可以，但是vector是连续空间的，所以为了更符合题意选择了list。
插入时，通过迭代器找到元素的位置，然后在后面insert数组。
删除时，也是通过迭代器找到元素的位置，erase删除。
也就是删除和插入都需要位置信息pos。

//两个一组 a b 表示b后面插入a
#include<iostream>
#include<list>//stl库，list是双向链表
using namespace std;
int main(){
    int num,head;
    cin>>num>>head;
    list<int> mylist;
    mylist.push_front(head);//在开头放入头结点
    list<int>::iterator it;
    for(int i=0;i<num-1;i++){
        int a,b;
        cin>>a>>b;
        for(it=mylist.begin();it!=mylist.end()&&*it!=b;it++);//遇到等于b时候停止，it指向b元素
        mylist.insert(++it,a);//注意是在b的后面插入a，所以++it
    }
    int k;
    cin>>k;
    for(it=mylist.begin();it!=mylist.end()&&*it!=k;it++);//找到k目标元素的位置
    mylist.erase(it);
    for(it=mylist.begin();it!=mylist.end();it++)//输出链表内容
        cout<<*it<<' ';
}

方法2：

自己写链表

//两个一组 a b 表示b后面插入a
#include<iostream>
using namespace std;
struct ListNode {
    int val;
    ListNode* next = nullptr;
};
class list {
public:
    ListNode* creat(int firstmem) {//给出第一个结点的数据域，返回头结点（头结点不存储数据）
        ListNode* head = new ListNode;
        head->next = new ListNode;
        head->next->val = firstmem;
        return head;
    }
    void insert(ListNode* head, int a, int b) {//在b后面插入a
        ListNode* p = head->next;//要从第一个结点开始搜索
        while (p && p->val != b) p = p->next;
        ListNode* q = new ListNode;
        q->val = a;
        q->next = p->next;
        p->next = q;
    }
    void erase(ListNode* head, int k) {//删除k
        ListNode* p = head;//要从第一个结点的前一个开始搜索
        while (p && p->next->val != k) p = p->next;
        ListNode* q = p->next;
        p->next = p->next->next;
        delete(q);
    }
    void print(ListNode* head) {//打印链表内容
        ListNode* p = head->next;
        while (p) {
            cout << p->val << ' ';
            p=p->next;
        }
    }
};


int main() {
    int num, headnum;
    cin >> num >> headnum;
    list L;
    ListNode* head = L.creat(headnum);//创建链表
    for (int i = 0; i < num-1; i++) {
        int a, b;
        cin >> a >> b;
        L.insert(head,a,b);//添加结点
    }
    int k; cin >> k;
    L.erase(head,k);//删除结点
    L.print(head);//打印结点数据域
}