链表——双向链表

题目描述

实现一个双链表，双链表初始为空，支持 5 种操作：
(1) 在最左侧插入一个数；
(2) 在最右侧插入一个数；
(3) 将第 k 个插入的数删除；
(4) 在第 k 个插入的数左侧插入一个数；
(5) 在第 k 个插入的数右侧插入一个数
现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。
注意：题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…，第 n 个插入的数。

输入格式

第一行包含整数 M (1≤M≤100000)，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
(1) L x，表示在链表的最左端插入数 x。
(2) R x，表示在链表的最右端插入数 x。
(3) D k，表示将第 k 个插入的数删除。
(4) IL k x，表示在第 k 个插入的数左侧插入一个数。
(5) IR k x，表示在第 k 个插入的数右侧插入一个数。
保证所有操作保证合法。

输出格式

共一行，将整个链表从左到右输出。

输入样例

10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2

输出样例

8 7 7 3 2 9

注释版代码

//http://47.110.135.197/problem.php?id=4613
#include<iostream>
#include<string>
using namespace std;
const int N=1e5+10;
int r[N],e[N],l[N];
int k,x,idx;
void init()
{r[0]=1,l[1]=0;idx=2;//双向链表初始化是将0看作头节点，1看作尾节点，那0和1都用了之后，idx得从2开始
}
//下面这个函数是在k的右边插入x，只需要定义这一个函数就可以了
//原因是因为在左端点插入x的话就是在0“右边插入”
//在右端点插入x的话就是在1的左边插入，就是相当于在1的前一位的“右边插入”
//在左边插入，就是相当于在前一位的“右边插入”
//所以这几种操作都可以用右边插入来解决
void add(int k,int x)
{//总结下来就从这几方面来考虑：//①想办法把x插进去，先处理x的右边，再处理左边//②x插入之后，想办法整理两边的逻辑，先整理右边的，再整理左边//分不清左右的时候都试试，然后发现下一步要用的值再前一步变化了，那就不对e[idx]=x;r[idx]=r[k];l[idx]=k;l[r[k]]=idx;r[k]=idx++;
}
//删除第k个
void remove(int k)
{r[l[k]]=r[k];l[r[k]]=l[k];
}
int main()
{init();int m;cin>>m;while(m--){string op;cin>>op;if(op=="L") cin>>x,add(0,x);else if(op=="R") cin>>x,add(l[1],x);else if(op=="D") cin>>k,remove(k+1);else if(op=="IL") cin>>k>>x,add(l[k+1],x);else if(op=="IR") cin>>k>>x,add(k+1,x);}for(int i=r[0];i!=1;i=r[i]){cout<<e[i]<<' ';}cout<<endl;return 0;
}