题目

来源

18. 链表的基本操作

思路

与上一份的最大区别就是要先判断一下要处理的k是否是合法的，也就是要先将指针能够指向k；

上一份的idx是一个全局的指针，由于链表天生就是物理位置不用连续，所以idx可以在任意位置，只要该节点能够和整个链表连接起来就行；

掌握数组模拟链表的基本用法，其他详见代码。

1. init 函数：初始化链表，将头指针 head 置为 -1，表示链表为空，同时将节点索引 idx 置为 0。
2. add2head 函数：将元素插入到链表头部，更新节点信息和头指针。
3. add2k 函数：在指定索引 k 后插入元素 x，更新节点的后继关系。
4. del2k 函数：删除指定索引 k 后的节点，跳过该节点更新后继关系。
5. display 函数：遍历链表并输出元素，如果链表为空则输出相应提示。
6. get2k 函数：遍历链表找到第 k 个元素并输出，若未找到则输出 "get fail"。
7. getIndex 函数：遍历链表找到第 k 个节点的索引，若未找到则返回 -1。
8. main 函数：
   • 读取输入的元素个数 n 并初始化链表，将元素倒序插入到链表头部。
   • 读取操作次数 m，根据不同操作类型执行相应操作，并输出操作结果。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int head, e[N], ne[N], idx;// 初始化链表
void init() {head = -1;idx = 0;
}// 插入到链表头部
void add2head(int x) {e[idx] = x;ne[idx] = head;head = idx;idx++;
}// 在指定索引 k 后插入元素 x
void add2k(int k, int x) {e[idx] = x;ne[idx] = ne[k];ne[k] = idx;idx++;
}// 删除指定索引 k 后的节点
void del2k(int k) {ne[k] = ne[ne[k]];
}// 显示链表元素
void display() {if (head == -1) {cout << "Link list is empty" << endl;} else {for (int i = head; i != -1; i = ne[i]) {cout << e[i] << " ";}cout << endl;}
}// 获取第 k 个元素
void get2k(int k) {int cnt = 0;for (int i = head; i != -1; i = ne[i]) {cnt++;if (cnt == k) {cout << e[i] << endl;return;}}cout << "get fail" << endl;
}// 获取第 k 个节点的索引
int getIndex(int k) {int cnt = 0;int cur = head;while (cur != -1) {cnt++;if (cnt == k) {return cur;}cur = ne[cur];}return -1;
}int main() {int n;cin >> n;init();// 倒序插入元素到链表头部for (int i = 0; i < n; i++) {int x;cin >> x;add2head(x);}int m;string op;cin >> m;while (m--) {cin >> op;if (op == "show") {display();} else if (op == "delete") {int k;cin >> k;if (k == 1) { //相当于从头结点插入if (head != -1) {head = ne[head];cout << "delete OK" << endl;} else {cout << "delete fail" << endl;}} else {int preIndex = getIndex(k - 1); //取第k个指针是否存在if (preIndex != -1) { //需要有得删，简单来说就是K要存在del2k(preIndex);cout << "delete OK" << endl;} else {cout << "delete fail" << endl;}}} else if (op == "insert") {int k, x;cin >> k >> x;if (k == 1) {add2head(x);cout << "insert OK" << endl;} else {int preIndex = getIndex(k - 1);if (preIndex != -1) { //k存在add2k(preIndex, x);cout << "insert OK" << endl;} else {cout << "insert fail" << endl;}}} else if (op == "get") {int k;cin >> k;get2k(k);}}return 0;
}