# 单向链表 ## 题目描述 实现一个数据结构，维护一张表（最初只有一个元素 $1$）。需要支持下面的操作，其中 $x$ 和 $y$ 都是 $1$ 到 $10^6$ 范围内的正整数，且保证任何时间表中所有数字均不相同，操作数量不多于 $10^5$： - `1 x y` ：将元素 $y$ 插入到 $x$ 后面； - `2 x` ：询问 $x$ 后面的元素是什么。如果 $x$ 是最后一个元素，则输出 $0$； - `3 x`：从表中删除元素 $x$ **后面的那个元素**，不改变其他元素的先后顺序。 ## 输入格式 第一行一个整数 $q$ 表示操作次数。 接下来 $q$ 行，每行表示一次操作，操作具体间题目描述。 ## 输出格式 对于每个操作 2，输出一个数字，用换行隔开。 ## 样例 #1 ### 样例输入 #1 ``` 6 1 1 99 1 99 50 1 99 75 2 99 3 75 2 1 ``` ### 样例输出 #1 ``` 75 99 ```

这道题目可以使用链表来实现。链表是一种常见的线性数据结构，它由多个节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。在单向链表中，每个节点只有一个指向下一个节点的指针。

对于每个操作，我们需要根据题目要求来实现相应的链表操作。以下是代码实现：

#include <iostream>
#include <unordered_map>

using namespace std;

const int N = 1000010;

struct Node
{
    int val;
    int next;
}node[N];

int idx = 0; // 链表的节点数量
unordered_map<int, int> pos; // 哈希表，用于记录每个节点的位置

// 在x节点后面插入一个值为val的节点
void insert(int x, int val)
{
    if (!pos.count(x)) return; // 如果x节点不存在，直接返回
    int p = pos[x]; // 找到x节点的位置
    node[++idx] = {val, node[p].next}; // 创建一个新节点，插入到x节点后面
    node[p].next = idx; // 修改x节点的next指针
    pos[val] = idx; // 将新节点的位置存入哈希表
}

// 删除x节点后面的节点
void remove(int x)
{
    if (!pos.count(x)) return; // 如果x节点不存在，直接返回
    int p = pos[x]; // 找到x节点的位置
    if (node[p].next == -1) return; // 如果x节点后面没有节点，直接返回
    int q = node[p].next; // 找到x节点后面的节点的位置
    node[p].next = node[q].next; // 删除x节点后面的节点
    pos.erase(node[q].val); // 删除被删除的节点的位置
}

// 查询x节点后面的节点的值
int query(int x)
{
    if (!pos.count(x)) return -1; // 如果x节点不存在，返回-1
    int p = pos[x]; // 找到x节点的位置
    if (node[p].next == -1) return 0; // 如果x节点后面没有节点，返回0
    int q = node[p].next; // 找到x节点后面的节点的位置
    return node[q].val; // 返回x节点后面的节点的值
}

int main()
{
    int q;
    cin >> q;

    // 初始化链表
    node[0] = {0, -1};
    pos[1] = 0;
    idx++;

    while (q--)
    {
        int op, x, y;
        cin >> op >> x;
        if (op == 1)
        {
            cin >> y;
            insert(x, y);
        }
        else if (op == 2)
        {
            cout << query(x) << endl;
        }
        else
        {
            remove(x);
        }
    }

    return 0;
}