AcWing 826. 单链表
原题链接
简单
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
typedef long long ll;
using namespace std;
const int N = 10e4 + 10;
const int Mod = 998244353;
int e[N], ne[N], idx, head;
//e 节点的值,ne 节点的next指针是多少,idx 当前链表已经存储到哪里了
void init() {
head = -1;
idx = 0;
}
void add_to_head(int x) {
e[idx] = x, ne[idx] = head, head = idx, idx++;
}
void add_to_k(int x, int k) {
e[idx] = x, ne[idx] = ne[k], ne[k] = idx, idx++;
}
void remove(int k) {
ne[k] = ne[ne[k]];
}
int main() {
int m;
cin >> m;
init();
for (int i = 0; i < m; i++) {
char action;
int k, x;
cin >> action >> k;
if (action == 'H') add_to_head(k);
else if (action == 'D') {
if (k == 0) head = ne[head];
else remove(k - 1);
}
else {
cin >> x;
add_to_k(x, k - 1);
}
}
for (int i = head; i != -1; i = ne[i]) {
cout << e[i] << " ";
}
return 0;
}
idx能够代表当前存入的是第几个值,所以删除的时候能直接通过idx找到要找的第k个值