AcWing 826. 单链表
原题链接
简单
作者:
Sky_
,
2020-11-15 10:57:07
,
所有人可见
,
阅读 359
#include <iostream>
//#include <algorithm>
using namespace std;
const int maxlen = 100000;
int e[maxlen], ne[maxlen]; //e数组用来存放元素, ne存放对应的尾指针
int head, idx; //初始化节点 head置为-1, idx记录了使用了多少个节点;
void init()
{
head = -1;
idx = 0;
}
void add_head(int x)
{
e[idx] = x; ne[idx] = head; head = idx++;
}
void add(int k, int x)
{
e[idx] = x; //第idx个数置为x
ne[idx] = ne[k]; //将idx数字后的指针转到插入数字后的指针
ne[k] = idx++; //原先第k个数指向新插入的数字
}
void remove(int k) //删除第k个元素后的元素
{
ne[k] = ne[ne[k]];
}
int main()
{
init();
int T;
cin>>T;
while(T--)
{
char op;
int k, x;
cin>>op;
if(op=='H')
{
cin>>x;
add_head(x);
}
else if(op=='I')
{
cin>>k>>x;
add(k-1, x);
}
else if(op=='D')
{
cin>>k;
if(!k) head=ne[head];
remove(k-1);
}
}
for(int i = head; i!=-1; i = ne[i]) cout<<e[i]<<" ";
return 0;
}