正常插入插入的值按顺序放入val数组当中
ne数组用来记录链表第k个数的下一位在val数组当中的位置。
h代表链表的头。初始值要定义成-1,才能不停地在ne数组中传递下去,代表链表终止的条件。
idx表示顺序插入数组的数字
删除链表中第k位的元素并非真实删除val中的数字,而是将ne[k-1]=ne[k]。这样链表就会绕过这个点,到下一个点。
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long ll;
const int M=100000+10;
ll h=-1,val[M],ne[M],idx;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll m;
cin>>m;
memset(ne,-1,sizeof ne);
while(m--)
{
char ch;
ll k,x;
cin>>ch;
if (ch=='H') //添加头
{
cin>>x;
ne[idx]=h;
h=idx;
val[idx++]=x;
}
else if (ch=='D') //删除
{
cin>>k;
if (k==0) //删除头
{
h=ne[h];
}
else //删除的非头
ne[k-1]=ne[ne[k-1]];
}
else //插入元素到链表尾部
{
cin>>k>>x;
val[idx]=x;
ne[idx]=ne[k-1];
ne[k-1]=idx++;
}
}
for (ll i=h;i!=-1;i=ne[i]) //用ne来遍历输出链表
cout<<val[i]<<' ';
}
联系客服