题解 | #【模板】链表#

• 因为是前插，所以遍历时要找到下一个节点值为x的节点，用cur记录下来，然后p指向新插入的节点，新插入的节点再指向p的next，同时要注意处理尾节点插入的状况，直接插入。
• 删除操作，直接跳过要删除的那个节点，并用delete安全删除

#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x){}
};
void insert(ListNode* pHead,int x,int y){//函数参数：当前链表pHead，插入位置x，插入的值y
    // ListNode* cur = pHead;
    ListNode* p = pHead;
    while (p!=nullptr&&p->next) {
        if(p->next->val==x){
            ListNode* add = new ListNode(y);
            ListNode* cur = p->next;
            p->next = add;
            add->next = cur;
            return;
        }
        p = p->next;
    }
    // 处理链表末尾插入新节点的情况
    ListNode* add = new ListNode(y);
    p->next = add;
    add->next = nullptr;
}
void del(ListNode* pHead,int x){
    ListNode* p = pHead;
    while (p->next&&p!=nullptr) {
        if(p->next->val==x){
            ListNode* temp = p->next;
            p->next = p->next->next;
            delete temp;
            return;
        }
    p = p->next;
    }
}

int main() {
    int n;
    cin>>n;
    ListNode* head = new ListNode(0);
    ListNode* p = head;  // 创建一个额外的指针来遍历链表
    for(int i = 0; i < n; i++)
    {
        string op;
        cin>>op;
        if(op == "insert")
        {
            int x, y;
            cin>>x>>y;
            insert(head, x, y);
        }
        if(op == "delete")
        {
            int x;
            cin>>x;
            del(head, x);
        }
    }
    if (head->next == nullptr) {  // 检查链表是否为空
        cout << "NULL";
    }
    
    p = head->next;  // 操作完后，将指针指向链表的第一个节点
    while (p != nullptr) {  // 遍历链表并输出节点的值
        cout << p->val << " ";
        p = p->next;
    }
    
    return 0;
}