AcWing 826. 单链表
原题链接
简单
作者:
月下邂逅
,
2024-04-25 14:44:54
,
所有人可见
,
阅读 1
C++ 代码
#include<iostream>
using namespace std;
const int N=100010;
int e[N],nt[N],head,idx,x,k;//用数组表示节点的时候会浪费空间,既删除的节点不会被释放
void init()//初始化链表
{
head=-1;
idx=0;
}
//k-1是因为下标从0开始
void insert(int k,int x)//第k个插入的数的后面,只需要将e[k-1]的nt指针指向当前位置,当前节点的nt指针指向原来e[k-1]的nt指针指向的位置
{
e[idx]=x;
nt[idx]=nt[k-1];
nt[k-1]=idx++;
}
void insert_head(int x)
{
e[idx]=x;//新头节点赋值
nt[idx]=head;//指向原本的头节点
head=idx++;//更新头节点指针
}
void Del(int k)//删除的是第k个插入的数后面的数,也就是e[k-1]节点的后一节点,只需要将e[k-1]的nt指针指向e[k]的nt指针指向的数
{
if(k==0)//k==0时删除头节点,只需要将当前头节点指针指向下一位置
{
head=nt[head];
return;
}
nt[k-1]=nt[nt[k-1]];
}
void printNode()
{
for(int i=head;i!=-1;i=nt[i])
{
printf("%d ",e[i]);
}
}
int main()
{
int n;
char s;
scanf("%d",&n);
init();
for(int i=0;i<n;i++)
{
//cin>>s;
scanf(" %c",&s);//%c前面需要一个空格以吸收上次输入缓冲区中的换行
if(s=='H')
{
scanf("%d",&x);
insert_head(x);
}
else if(s=='I')
{
scanf("%d",&k);
scanf("%d",&x);
insert(k,x);
}
else if(s=='D')
{
scanf("%d",&k);
Del(k);
}
}
printNode();
return 0;
}