AcWing 826. 单链表
原题链接
简单
作者:
Asteroid.W
,
2021-08-26 22:01:04
,
所有人可见
,
阅读 223
#include <iostream>
using namespace std;
const int N = 100010;
// head 表示头结点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少,也就是指向下一个节点
// idx存储当前已经用到了哪个点
int head, e[N], ne[N], idx;
//初始化
void init() {
head = -1; // -1表示null
idx = 0; // 从[0]位置开始
}
// 将x插到头结点
void add_to_head(int x) {
e[idx] = x; // 把值赋到数据域
ne[idx] = head; // 然后让head的地址值存入指针域
head = idx++; // //更新头结点,头结点指向插入的节点下标,再让idx向下移一位,让idx始终指向一个空位置
}
// 将x插到下标是k的后面
void add(int k, int x) {
e[idx] = x;
ne[idx] = ne[k]; // 将idx指向k节点的后面
ne[k] = idx++; // 将k的next指向idx,再让idx向下移动一位
}
//将下标是k的点后面的点删掉
void remove(int k) {
ne[k] = ne[ne[k]]; //让k的next指向下个结点的下个结点,就相当于把k后面的哪个点删除了
}
int main() {
int m;
cin >> m;
init(); // 初始化操作
while(m--) {
int k, x;
char op;
cin >> op;
if(op == 'H'){
cin >> x;
add_to_head(x);
}
else if(op == 'D'){
cin >> k;
if(!k) head = ne[head]; //特判, k为0时,即去掉头结点:删除头结点应该是将第一个节点跳过去:head = ne[head]。
else remove(k - 1); // 不是头结点时,从0开始,k要减去1
}
else {
cin >> k >> x;
add(k - 1, x); // 第k个结点的下标为k-1,所以插入到下标为 k-1结点的后面(因为k从0开始)
}
}
// head = -1表示空。head存的是头结点的下标,从头结点开始遍历
// 在初始化函数init中,head=-1啊,这个-1代码保证一直在尾部
for (int i = head; i != -1; i = ne[i]) {
cout << e[i] << ' ';
}
cout << endl;
return 0;
}