AcWing 826. 单链表(注释解释版本)
原题链接
简单
作者:
Misakiii
,
2021-01-17 16:40:36
,
所有人可见
,
阅读 398
C++ 代码
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
/*说明:head是初学者经常出错的一个地方,
head不是节点,只是指向某个节点的指针,head存的是链表第一个点的下标
初始化的时候head为-1,说明整个链表为空
e[i]表示节点i的值
ne[i]表示节点i的next指针指向哪里
idx存储当前已经用到了哪个点
*/
int head, e[N], ne[N], idx;
//初始化
void init(){
head = -1; //表示链表为空
idx = 0;
}
//将x插入到头结点(也就是插入到头结点位置)
void add_to_head(int x){
e[idx] = x; //先存下x
ne[idx] = head; //让插入的节点指向head指向的节点
head = idx++; //让head指向该节点,并移动该节点指针
}
//将x插入到下标是k的节点后面
void add(int k ,int x){
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx++;
}
//将下标为k的节点的后面一个节点删除
void remove(int k){
ne[k] = ne[ne[k]]; //简单粗暴
}
int main(){
int M;
cin >> M;
init(); //初始化别忘了
while(M--){
char op;
cin >> op;
if(op == 'H'){
int x;
cin >> x;
add_to_head(x);
}
else if(op == 'I'){
int k, x;
cin >> k >> x;
add(k - 1, x); //下标从0开始,k要减一
}
else{
int k;
cin >> k;
if(!k) head = ne[head]; //如果删除第一个节点就要特判
else remove(k - 1);
}
}
//注意这个遍历的写法
for(int i = head; i != -1; i = ne[i])
cout << e[i] << ' ';
cout << endl;
return 0;
}