题目描述
单链表
代码思路
在链表中使用虚设节点 , 规约节点范围 ,减少边界条件
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int M = 1e5 + 3;
int e[M] , ne[M] , idx;
void init() {
// 虚设节点 1 -> 0
ne[1] = 0;
idx = 2;
}
void remove(int k ) {
ne[k] = ne[ne[k]];
}
void insert(int k , int x) {
e[idx] = x , ne[idx] = ne[k] , ne[k] = idx ++ ;
}
int m;
int main() {
ios::sync_with_stdio(false);
cin >> m ;
init();
while (m -- ) {
char op ; cin >> op ;
if(op == 'H') {
int x ; cin >> x; insert(1 , x);
}else if(op == 'I') {
int k , x; cin >> k >> x;
insert(k + 1 ,x );
}else if(op == 'D') {
int k ; cin >> k ; remove(k + 1);
}
}
int p = ne[1];
while(p) {
cout << e[p] << ' ';
p = ne[p];
}
cout << endl;
return 0;
}