AcWing 23. 双链表
原题链接
简单
作者:
第一次的约会
,
2023-11-13 19:30:20
,
所有人可见
,
阅读 49
相比于单链表新加了一个指向前面数的指针
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int e[N], idx,l[N],r[N];
//初始化
void index()
{
r[0] = 1;
l[1] = 0;
idx = 2;
}
//从k的右边插入
void add(int k,int x)
{
e[idx] = x;
//先操作新加入的点
l[idx] = k;
r[idx] = r[k];
//再操作左右两边
l[r[k]] = idx;
r[k] = idx;
idx++;
}
//也可以从k的左边插入,只需要传入参数为(int l[k],int x)就行
//删除第k个数
void del(int k)
{
l[r[k]] = l[k];
r[l[k]] = r[k];
}
void show()
{
int k = r[0];
while (k != 1)
{
printf("%d ", e[k]);
k = r[k];
}
}
int main()
{
int m;
cin>>m;
index();
for(int i=1;i<=m;i++)
{
string c;
cin >> c;
if (c == "L")
{
int x;
cin >> x;
add(0, x);
}
else if (c == "R")
{
int x;
cin >> x;
add(l[1], x);
}
else if (c == "D")
{
int k;
cin >> k;
del(k+1);//因为数组下标起始是从2开始的,相当于k-1+2
}
else if (c == "IL")//因为是两个字符,所以要用string
{
int k, x;
cin >> k >> x;
add(l[k+1], x);
}
else if (c == "IR")
{
int k, x;
cin >> k >> x;
add(k+1, x);
}
}
show();
return 0;
}