精品网站模板,怎么在网站底部做备案号,e站注册网站,网页设计做一个网站文章目录 QuestionIdeasCode Question
实现一个双链表#xff0c;双链表初始为空#xff0c;支持 5 种操作#xff1a;
在最左侧插入一个数#xff1b; 在最右侧插入一个数#xff1b; 将第 k 个插入的数删除#xff1b; 在第 k 个插入的数左侧插入一个数#xff1b; … 文章目录 QuestionIdeasCode Question
实现一个双链表双链表初始为空支持 5 种操作
在最左侧插入一个数 在最右侧插入一个数 将第 k 个插入的数删除 在第 k 个插入的数左侧插入一个数 在第 k 个插入的数右侧插入一个数 现在要对该链表进行 M 次操作进行完所有操作后从左到右输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数则按照插入的时间顺序这 n 个数依次为第 1 个插入的数第 2 个插入的数…第 n 个插入的数。
输入格式 第一行包含整数 M 表示操作次数。
接下来 M 行每行包含一个操作命令操作命令可能为以下几种
L x表示在链表的最左端插入数 x 。 R x表示在链表的最右端插入数 x 。 D k表示将第 k 个插入的数删除。 IL k x表示在第 k 个插入的数左侧插入一个数。 IR k x表示在第 k 个插入的数右侧插入一个数。 输出格式 共一行将整个链表从左到右输出。
数据范围 1≤M≤100000
所有操作保证合法。
输入样例 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
Ideas
Code
#include iostream
#include stringusing namespace std;
const int N 1E5 10;
int e[N], l[N], r[N], idx;void init(){r[0] 1;l[1] 0;idx 2;
}void add(int k, int x){e[idx] x;r[idx] r[k];l[idx] k;l[r[k]] idx;r[k] idx;idx ;
}void del(int k){r[l[k]] r[k];l[r[k]] l[k];
}
int main(){int m;cin m;init();while(m --){string op;cin op;if (op L){int x; cin x;add(0, x);}else if (op R){int x;cin x;add(l[1], x);}else if(op D){int k;cin k;del(k 1);}else if (op IL){int k, x;cin k x;add(l[k 1], x);}else{int k, x;cin k x;add(k 1, x);}}for (int i r[0]; i ! 1; i r[i]) cout e[i] ;return 0;
}
