AcWing 826. 单链表
原题链接
简单
作者:
神的在场证明
,
2024-04-21 16:44:17
,
所有人可见
,
阅读 1
样例
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int m;
int head, idx, h[N], e[N], ne[N];
void init(){ //初始化
head = -1; // 最开始 链表头节点要指向-1(即指向空), 表示链表里没有内容 ; 当链表里有元素时,变成指向第一个元素的指针 指向头节点
//目的是 在后续的操作中 知道链表什么时候结束
idx = 0; //作为链表的下标
}
//将x插入到链表头节点。。
void add_to_head(int x){ //和链表中间插入的区别在于 他有head头节点
e[idx] = x; //将x的值放入节点中
ne[idx] = head; //将元素x的指针 指向head原本的指向
head = idx; //表示head 指向第一个元素,不再是空指针了
idx++; //指针下移一位,为下一次插入元素做准备
}
//将x插入到下标为k的节点后面
void add(int k, int x){
e[idx] = x; //将x值放入节点
ne[idx] = ne[k]; //将元素 x的指针 指向原本下标为k的节点 指针的指向位置
ne[k] = idx; //让原来的指针(下标为k节点的指针) 指向当前元素x
idx++; //指针 后移
}
void remove(int k){ //删除第k个插入的数的后面的数
if(k == -1){ //删除头结点 下标减一
head = ne[head];
} else{
ne[k] = ne[ne[k]]; //让k指向 k下一个针的 下一个指针
}
}
//下标 减一
int main(){
cin >> m;
init();
while(m--){
char op;
int k, x;
cin >> op;
if(op == 'H'){
cin >> x;
add_to_head(x); //向链表头插入一个元素x
}else if(op == 'D'){
cin >> k;
remove(k-1); //删除第k个插入数后面的数
}else{
cin >> k >> x;
add(k-1,x);//在第k个插入数后面插入数x
}
}
for(int i = head; i != -1; i = ne[i]){
cout << e[i] << " ";
}
puts("");
return 0;
}