题解 | #【模板】链表#

#include <iostream>
using namespace std;

class Node
{
public:
    Node* next;
    int data;
    Node(int val)
    {
        data = val;
        next = nullptr;
    }
};

class LinkedList
{
private:
    Node* head;
    
public:
    LinkedList()
    {//带头结点
        head = new Node(0);
    }

    void insert_x_y(int x, int y)
    {
        Node* preNode = head;
        Node* curNode = head->next;

        while(curNode != nullptr && curNode->data != x)
        {//寻找值为x的结点
            preNode = curNode;
            curNode = curNode->next;
        }

        if(curNode == nullptr)
        {//不存在值为x的结点，则尾插
            Node* newNode = new Node(y);
            preNode->next = newNode;
        }
        else {//存在值为x的结点，插至当前节点之前
            Node* newNode = new Node(y);
            preNode->next = newNode;
            newNode->next = curNode;
        }
        return;
    }

    void delete_x(int x)
    {
        Node* preNode = head;
        Node* curNode = head->next;

        while(curNode != nullptr && curNode->data != x)
        {
            preNode = curNode;
            curNode = curNode->next;
        }
        if(curNode == nullptr)
        {
            return;
        }
        Node* deleNode = curNode;
        curNode = curNode->next;
        preNode->next = curNode;
        delete deleNode;
    }

    void outputAll()
    {
        Node* curNode = head->next;
        if(head == nullptr || curNode == nullptr)
        {//链表为空
            cout << "NULL";
            return;
        }
        while(curNode != nullptr)
        {
            cout << curNode->data << ' ';
            curNode = curNode->next;
        }
    }
};

int main() {
    int n;
    LinkedList linkedList;
    cin >> n;
    for(int i = 0;i < n;++i)
    {
        string operation;
        cin >> operation;
        if(operation == "insert")
        {
            int x, y;
            cin >> x >> y;
            linkedList.insert_x_y(x, y);
        }
        else if (operation == "delete") {
            int x;
            cin >> x;
            linkedList.delete_x(x);
        }
        else {
            cout << "error" << endl;
        }
    }

    linkedList.outputAll();
}
// 64 位输出请用 printf("%lld")