算法1
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int e[N],ne[N],head;
int idx;
void init(){
head = -1;
idx = 0;
}
void add_head(int x){
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
void del(int k){
ne[k] = ne[ne[k]];
}
void insert(int k,int x){
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
int main(){
int number;
cin>>number;
//memset(ne,0x3f,sizeof(ne));
init();
while (number -- )
{
int k, x;
char op;
cin >> op;
if (op == 'H')
{
cin >> x;
add_head(x);
}
else if (op == 'D')
{
cin >> k;
if (!k) head = ne[head];
else del(k - 1);
}
else
{
cin >> k >> x;
insert(k - 1, x);
}
}
for(int i=head;i!=-1;i=ne[i])
cout<<e[i]<<" ";
//由于最开始的时候,初始化head为-1,在进行头插法建立链表的过程中,最后一个节点的ne值一定是-1
}