题解 | #【模板】链表#

本题主要进行 在指定位置插入节点 以及 删除指定位置节点 的链表操作的模拟（本题解使用带头节点的链表）

首先在结构体中定义用于存储节点数据的data和用于指向下一个节点的结构体指针next。

对于插入操作，需要在第一次出现指定值的节点之前的位置进行节点的插入，因此需要两个指针，p指针向后遍历链表寻找指定值节点，q指针跟随在p指针之前，以便于新节点的插入。当p指针找到指定值节点或为空时，便new一个新节点，将其插入到q节点之后即可。

对于删除操作，与插入操作类似，依然需要p和q两个指针，当p指针找到指定位置后，将q指针的next指向p指针的next，然后将p指针的next置空，即可delete p，达到删除指定位置节点的要求。

#include<iostream>
using namespace std;
struct List
{
    int data;
    List* next;
};
void insert(List* p, int x, int y) // 在指定位置插入节点
{
    List* q = p;
    p = p->next;
    while(p != NULL)
    {
        if(p->data == x)
        {
            break;
        }
        q = p;
        p = p->next;
    }
    List* t = new List();
    t->data = y;
    q->next = t;
    t->next = p;
}
void del(List* p, int x) // 删除指定位置节点
{
    List* q = p;
    p = p->next;
    while(p != NULL)
    {
        if(p->data == x)
        {
            q->next = p->next;
            p->next = NULL;
            delete p;
            return ;
        }
        q = p;
        p = p->next;
    }
}
int main()
{
    int n;
    cin>>n;
    List* head = new List();
    head->next = NULL; // 创建带头节点的链表
    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);
        }
    }
    List* f = head->next; // 因为带头节点，因此需要从head->next开始遍历链表
    if(f == NULL)
    {
        cout<<"NULL";
    }
    while(f != NULL)
    {
        cout<<f->data<<" ";
        f = f->next;
    }
    return 0;
}