单向链表(Singly Linked List) 题解

思路分析

由于任意时刻表中所有数字均在 $[1, 10^6]$ 内且互不相同，直接用值作为下标开设 nxt[1000005] 数组维护单向链表后继指针即可：插入 1 x y 令 nxt[y] = nxt[x], nxt[x] = y；查询 2 x 输出 nxt[x]（表尾天然为 0）；删除 3 x 若 nxt[x] != 0 则令 nxt[x] = nxt[nxt[x]]。单次操作 $O(1)$，总时间复杂度 $O(q)$。

参考代码

#include <iostream>
using namespace std;

const int MX = 1000005;
int nxt[MX];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    if (!(cin >> q)) return 0;
    for (int i = 0; i < q; ++i)
    {
        int op, x;
        cin >> op >> x;
        if (op == 1)
        {
            int y;
            cin >> y;
            nxt[y] = nxt[x];
            nxt[x] = y;
        }
        else if (op == 2)
        {
            cout << nxt[x] << "\n";
        }
        else
        {
            if (nxt[x] != 0) nxt[x] = nxt[nxt[x]];
        }
    }
    return 0;
}