AcWing 826. 单链表
原题链接
简单
作者:
吃一波夜宵
,
2021-12-05 19:04:01
,
所有人可见
,
阅读 125
#include <iostream>
#include <stdio.h>
using namespace std;
int m, n;
const int N = 1e6 + 10;
// head 代表头结点的下标
// e【i】 代表的节点的值
// ne[i] 代表的节点i的next的值是多少,也就是下一节点的位置
// idx表示当前的节点
int head, e[N], ne[N], idx;
//初始化
void init()
{
head = -1;//最开始的时候head头结点指向-1,可以把head看成一个指针,它指向-1表示链表里没有节点
idx = 0; //idx代表当前的下标,在插入的时候可以更加方便的执行。 也为节点分配下标
}
//插入头结点
void add_to_head(int x)
{
e[idx] = x;
ne[idx] = head;//next指向-1
head = idx;//head 指向当前的下标
idx ++;
}
//删除第k个节点
void remove(int k)//画图的很好理解
{
ne[k] = ne[ne[k]];
}
//在第k个节点后面加入
void add(int k, int x)//画图的话很好理解
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx ++;
}
int main()
{
scanf("%d",&m);
int x, k;
init();
char op;
while(m --)
{
cin >> op;
if(op == 'H')
{
cin >> x;
add_to_head(x);
}
else if(op == 'D')
{
cin >> k;
if(!k) head = ne[head];//特判 如果咱们删的是头结点的时候,ne[head] 这个节点的ne【】是被删除的那个节点的ne【】。被删除的这个点是head,表示出下一个点用ne[head].
remove(k - 1);
}
else if(op == 'I')
{
cin >> k >> x;
add(k - 1, x);//删除第k个节点和下标差1,所以要减一
}
}
for(int i = head; i != -1; i = ne[i]) cout << e[i] <<" "; //遍历整个链表,用ne【i】 来遍历
return 0;
}