#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 998244353;
int m, e[N]/*存值*/, ne[N]/*存下一节点位置*/, head/*表头位置*/, idx/*当前已使用的节点数量*/;
void init() {//初始化
head = -1, idx = 0;
}
void add_to_head(int x) {
e[idx] = x, ne[idx] = head, head = idx++;
}
void remove(int k) {
ne[k] = ne[ne[k]];
}
void add(int k, int x) {
e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> m;
init();
while (m--) {
char op;
int k, x;
cin >> op;
switch (op) {
case 'H':
cin >> x;
add_to_head(x);
break;
case 'D':
cin >> k;
if (!k) head = ne[head];//若删表头,则直接将head重赋值为下一节点
else remove(k - 1);//因为是从0开始标号,使用需要k-1
break;
case 'I':
cin >> k >> x;
add(k - 1, x);//同上
break;
default:
break;
}
}
for (int i = head/*从头开始遍历链表*/; i != -1/*直到无下一节点*/; i = ne[i]) cout << e[i] << ' ';
return 0;
}
【模板】单链表
发布于 17 天前 1 次阅读
Comments | NOTHING