根据题目,我们可以使用三个数组来存储数值以及上一个、下一个的位置关系,并用变量存储列表第一个的位置。
a[]: 数值
prv[]: 上一个的位置
nxt[]: 下一个的位置,为特殊值的时候则表示它为最后一个
上AC代码。耗时~2h
#include <bits/stdc++.h>
using namespace std;
const int tail=114510;
int m,n,a[114514],prv[114514],nxt[114514],p,head;
int main(){
p=0;
memset(a,-1,sizeof(a));
memset(prv,0,sizeof(prv));
memset(nxt,0,sizeof(nxt));
cin>>m;
head=0;
for (int i=1; i<=m; i++){
char ch;
int x,y;
cin>>ch>>x;
if (ch=='I') cin>>y;
if (ch=='H'){
//p=new head; head=old head
p++;
a[p]=x; //generate new value
if (head==0) nxt[p]=tail; //give the new value a nxt
else nxt[p]=head;
prv[p]=0; //the new value shall not have a prv
if (head!=0) prv[head]=p; //the new value will become the old head's prv
head=p; //for now, head is also the new head
}
if (ch=='D'){
if (x==0){
int t=head;
prv[nxt[head]]=0;
head=nxt[head];
nxt[t]=0;
continue;
}
//x, target, x2
int t=nxt[x]; //target to delete
nxt[x]=nxt[t]; //attach x2 to x
//nxt[t] may be the tail
if (nxt[t]!=tail){
prv[nxt[t]]=x;
}
nxt[t]=0; //de-attach target from everything
prv[t]=0;
}
if (ch=='I'){
p++;
a[p]=y;
nxt[p]=nxt[x];
nxt[x]=p;
prv[p]=x;
if (nxt[p]!=tail) prv[nxt[p]]=p;
}
}
n=head;
/*
cout<<"HEAD: "<<head<<endl;
for (int i=1; i<=p; i++){
cout<<"VAL: "<<a[i]<<"; PREV: "<<prv[i]<<"; NEXT: "<<nxt[i]<<endl;
}*/
do{
cout<<a[n]<<" ";
n=nxt[n];
}
while (n!=tail);
return 0;
}