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

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
struct DlinkedNode{

    int val;
    DlinkedNode* pre;
    DlinkedNode* next;
    DlinkedNode(): val(0), pre(nullptr), next(nullptr){};
    DlinkedNode(int v): val(v),pre(nullptr),next(nullptr){};

};

int main(){
    unordered_map<int, DlinkedNode*> cache;
    string tmp;
    vector<int> inputs;
    while(getline(cin,tmp,' ')){
        inputs.push_back(stoi(tmp));        
    }
    int n = inputs[0];
    int first_val = inputs[1];
    DlinkedNode* head = new DlinkedNode();
    DlinkedNode* tail = new DlinkedNode();
    DlinkedNode* first = new DlinkedNode(first_val);
    cache[first_val] = first;
    head->next = first;
    first->pre = head;
    first->next = tail;
    tail -> pre = first;
    for(int i = 2; i < inputs.size()-1; i+=2){
//         cout << "cur i :" << i << endl;
        int back_val = inputs[i];
        int front_val = inputs[i+1];
//         cout << "front_val : " << front_val << endl;
//         cout << "back_val : " << back_val << endl;
        DlinkedNode* back_node = new DlinkedNode(back_val);
        cache[back_val] = back_node;
        DlinkedNode* front_node = cache[front_val];

        // 插入节点
        back_node->next = front_node->next;
        front_node->next->pre = back_node;
        back_node->pre = front_node;
        front_node->next = back_node;

    }

    DlinkedNode* cur = head;
    while(cur){
        if( cur->val == inputs.back() ){
            cur->pre->next = cur->next;
            cur->next->pre = cur->pre;
            break;
        }
        cur = cur->next;
    }

    DlinkedNode* res = head->next;
    if(res == tail)
        cout << "nullptr" << endl;
    while(res!=tail){
        cout << res->val << ' ';
        res = res->next;
    }


}