上海柘中建设股份有限公司网站,搜索引擎收录入口,专业网站制作推荐,seo优化排名营销目录 双链表代码 思路 双链表
实现一个双链表#xff0c;双链表初始为空#xff0c;支持 5 种操作#xff1a;
在最左侧插入一个数#xff1b; 在最右侧插入一个数#xff1b; 将第 k个插入的数删除#xff1b; 在第 k 个插入的数左侧插入一个数#xff1b… 目录 双链表代码 思路 双链表
实现一个双链表双链表初始为空支持 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
代码 思路
双链表就比单链表多一个指针 思路大差不差
#include iostreamusing namespace std;const int N 100010;int m;
int e[N], l[N], r[N], idx;// 在节点a的右边插入一个数x
void insert(int a, int x)
{e[idx] x; //第idx的节点的值为xl[idx] a, //第idx的节点左指针指向当前节点ar[idx] r[a]; //第idx的节点右指针指向a指针的右指针l[r[a]] idx, //a节点原右边节点的指针的左指针指向当前idx节点r[a] idx ; //a节点现在的右指针指向idx 并让idx 1
}// 删除节点a
void remove(int a)
{l[r[a]] l[a]; //a节点右边节点的左指针指向a节点的左节点r[l[a]] r[a]; //a节点的左节点的右指针指向a节点的右节点
}int main()
{cin m;// 0是左端点1是右端点r[0] 1, l[1] 0; //这是两个哨兵节点idx 2; //表示双链表里面初始有两个节点 其实就是哨兵节点 一个指向链表的头结点 一个指向链表的尾节点while (m -- ){string op;cin op;int k, x;if (op L){cin x;insert(0, x);}else if (op R){cin x;insert(l[1], x);}else if (op D){cin k;remove(k 1);}else if (op IL){cin k x;insert(l[k 1], x);}else{cin k x;insert(k 1, x);}}for (int i r[0]; i ! 1; i r[i]) cout e[i] ;cout endl;return 0;
}
