B3631 单向链表——题解

思路

由于元素值最大只有 $10^6$ 且互不相同，可以用数组 nxt[x] 直接记录元素 x 后面的元素。

• 插入 y 到 x 后面：先令 nxt[y]=nxt[x]，再令 nxt[x]=y；
• 查询 x 后面：输出 nxt[x]，末尾的后继本来就是 $0$；
• 删除 x 后面：令 nxt[x]=nxt[nxt[x]]。若 nxt[x]==0，数组的零号位置也为 $0$，操作自然保持不变。

复杂度

每条操作时间复杂度 $O(1)$，空间复杂度 $O(10^6)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

int nxt[1000005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;
    while (q--) {
        int op, x, y;
        cin >> op >> x;
        if (op == 1) {
            cin >> y;
            nxt[y] = nxt[x];
            nxt[x] = y;
        } else if (op == 2) {
            cout << nxt[x] << '\n';
        } else {
            nxt[x] = nxt[nxt[x]];
        }
    }
    return 0;
}

#include <bits/stdc++.h> using namespace std; int nxt[1000005]; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin>>q; while(q--){ int op,x,y; cin>>op>>x; if(op1){ cin>>y; nxt[y]=nxt[x]; nxt[x]=y; } else if(op2) cout<<nxt[x]<<'\n'; else nxt[x]=nxt[nxt[x]]; } return 0; }