AcWing 827. 双链表
原题链接
简单
C++ 代码
#include <iostream>
using namespace std;
const int N = 1e5 + 1;
int m, k, x, idx;
int e[N], ne[N], fe[N];
void init()
{
ne[0] = 1;
fe[1] = 0;
idx = 2;
}
void add_L(int x)
{
e[idx] = x;
ne[idx] = ne[0];
fe[idx] = 0;
fe[ne[0]] = idx;
ne[0] = idx ++;
}
void add_R(int x)
{
e[idx] = x;
ne[idx] = 1;
fe[idx] = fe[1];
ne[fe[1]] = idx;
fe[1] = idx ++;
}
void Delete(int k)
{
ne[fe[k + 1]] = ne[k + 1];
fe[ne[k + 1]] = fe[k + 1];
}
void il(int k, int x)
{
e[idx] = x;
ne[idx] = k + 1;
fe[idx] = fe[k + 1];
ne[fe[idx]] = idx;
fe[k + 1] = idx ++;
}
void ir(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k + 1];
fe[idx] = k + 1;
fe[ne[idx]] = idx;
ne[k + 1] = idx ++;
}
int main()
{
init();
cin >> m;
char c;
while (m -- )
{
cin >> c;
if(c == 'L')
{
cin >> x;
add_L(x);
}
else if(c == 'R')
{
cin >> x;
add_R(x);
}
else if(c == 'D')
{
cin >> k;
Delete(k);
}
else
{
char temp;
cin >> temp;
if(temp == 'L')
{
cin >> k >> x;
il(k, x);
}
else
{
cin >> k >> x;
ir(k, x);
}
}
}
for(int i = ne[0]; i != 1; i = ne[i]) cout << e[i] << ' ';
return 0;
}