AcWing 827. 双链表
原题链接
中等
作者:
落花已作风前舞
,
2024-04-25 23:49:24
,
所有人可见
,
阅读 1
#include <iostream>
using namespace std;
int const N = 1e5 + 10;
int l[N], r[N], e[N]; // 左指针数组,右指针数组,存值数组;
int idx; // 当前点的编号
// 链表的结构为:0 。。。。。。。。1
void init()
{
// 链表初始状态为0 1
// 0号点当头结点,1号点当尾结点,是两个哑点(空结点)
l[1] = 0; // 1号点的左边是0号点
r[0] = 1; // 0号点的右边是1号点
idx = 2; // 前面两个01号房子已经有人住了,所以idx指的是第三个房子,即记录当前下标
}
//删除第k个点
void remove (int k)
{
r[l[k]] = r[k]; // k - 1号点的右指针,指向的是k号点右指针指向的点(k + 1号点)
l[r[k]] = l[k]; //k + 1号的左指针,指向的是k号点左指针指向的点(k - 1号点)
}
// 在k点的右边插入数x
void insert(int k, int x)
{
e[idx] = x; // 先把x的值放进当前idx下标的结点中
r[idx] = r[k]; // idx结点的右指针指向k结点的下一个结点
l[idx] = k; // idx结点的左指针指向k结点
l[r[k]] = idx; // k结点指向的下一个结点的左指针指向idx结点
r[k] = idx; // k结点的右指针指向idx结点
idx ++; // idx指向下一个结点指标
}
// 在k点的左边插入插入x,即insert(int l[k], int x) !!!千万别写k-1,因为这是数组存的下标,数组序号并不是代表结点序号
// 所以用l[k], 表示的是k结点的左边结点
int main ()
{
int m;
cin >> m;
init();
while (m --)
{
string op;
int k, x;
cin >> op;
if (op == "L")
{
cin >> x;
insert(0, x);
}
else if (op == "R")
{
cin >> x;
insert(l[1], x); // 不是1, 在链表最右端插入x,表示是在1号结点的左边插入x
}
else if (op == "D")
{
cin >> k;
remove(k + 1); // 因为idx是从2开始的,第k个插入点的下标应该是k+1,
}
else if (op == "IL")
{
cin >> k >> x;
insert(l[k + 1], x);
}
else if (op == "IR")
{
cin >> k >> x;
insert(k + 1, x);
}
}
for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' '; // i = r[i], 就是相当于指向下一个结点
cout << endl;
return 0;
}