1.单链表：
实现一个单链表，链表初始为空，支持三种操作：
- 向链表头插入一个数；
- 删除第 k 个插入的数后面的一个数；
- 在第 k 个插入的数后插入一个数。
现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
H x，表示向链表头插入一个数 x。D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）。
输出格式
共一行，将整个链表从头到尾输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例：
10 H 9 I 1 1 D 1 D 0 H 6 I 3 6 I 4 5 I 4 5 I 3 4 D 6
输出样例：
6 4 6 5
代码：（链式前向星）
#include <iostream> #include <vector> #include <algorithm> using namespace std; const int N = 100010; // head表示头节点的下标 // e[i]表示节点i的值 // ne[i]表示节点i的next指针是多少 // i:编号 // idx存储当前已经用到了哪个点 int head, e[N], ne[N], idx; // 初始化 void init() { head = -1; idx = 0; } void add(int x) { // 头插 e[idx] = x; // 存数 ne[idx] = head; // 头插操作1：idx指向头节点 head = idx; // 头插操作2：头节点改成idx idx++; } // 将x插入到下标是k的点后面 void add(int k, int x) { e[idx] = x; // 存数 ne[idx] = ne[k]; // 操作1 ne[k] = idx; // 操作2 idx++; } // 将下标是k后面的点删除(单链表找后面的点好找) void remove(int k) { ne[k] = ne[ne[k]]; // 1->2->3,k=1,ne[1]=2,ne[ne[1]]=3 } int main() { int m; cin >> m; init(); while (m--) { int k, x; char op; cin >> op; if (op == 'H') { cin >> x; add(x); } else if (op == 'D') { cin >> k; if (k == 0) head = ne[head]; // 特判k=0 remove(k - 1); } else { cin >> k >> x; add(k - 1, x); } } for (int i = head; i != -1; i = ne[i]) { cout << e[i] << " "; } return 0; }
2.双链表
实现一个双链表，双链表初始为空，支持 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 <iostream> #include <vector> #include <algorithm> using namespace std; const int N = 100010; int m; int e[N], l[N], r[N], idx; // e:这个点的值 l:存左边的数 r:存右边的数 // 初始化 void init() { // 0表示左端点head,1表示右端点tail r[0] = 1; // 0号点的右边是1号点 l[1] = 0; idx = 2; } // 插入 void addr(int k, int x) { // k点右边插入x e[idx] = x; r[idx] = r[k]; l[idx] = k; r[k] = idx; l[r[idx]] = idx; idx++; // 不要忘记！！！ } void addl(int k, int x) { // k点左边插入x e[idx] = x; r[idx] = k; l[idx] = l[k]; l[k] = idx; r[l[idx]] = idx; idx++; // 不要忘记！！！ } // 删除 void remove(int k) { // 删除第k个点 r[l[k]] = r[k]; l[r[k]] = l[k]; } int main() { cin >> m; init(); // 易忘记！！！！ while (m--) { string op; cin >> op; int x, k; if (op == "L") // 也可都使用在右边插入（注释里） { cin >> x; addr(0, x); // 在头节点0的右边插入x } if (op == "R") { cin >> x; // addr(l[1], x); // 在尾节点左边插入x addl(1, x); } if (op == "D") { cin >> k; remove(k + 1); // 这里易错，k都变为k+1，因为idx初始为2 } if (op == "IL") { cin >> k >> x; // addr(l[k + 1], x); addl(k + 1, x); } if (op == "IR") { cin >> k >> x; addr(k + 1, x); } } for (int i = r[0]; i != 1; i = r[i]) // 从r[0]开始 { cout << e[i] << " "; } return 0; }
