826. 单链表

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int e[N],ne[N];
int head;
int idx;
void init()
{
	head=-1;
	idx=0;
}
void add_head(int x)
{
	e[idx]=x;
	ne[idx]=head;
	head=idx++;
}
void remove(int k)
{
	ne[k]=ne[ne[k]];
}
void add(int k,int x)
{
	e[idx]=x;
	ne[idx]=ne[k];
	ne[k]=idx++;
}
int main()
{
	init();
	int t;
	cin>>t;
	while(t--)
	{
		char s[10];
		cin>>s;
		if(s[0]=='H')
		{
			int x;
			cin>>x;
			add_head(x);
		}
		else if(s[0]=='D')
		{
			int k;
			cin>>k;
			if(k==0)	head=ne[head];
			else remove(k-1);
		}
		else
		{
			int k,x;
			cin>>k>>x;
			add(k-1,x);
		}
	}
	for(int i=head;i!=-1;i=ne[i])
	{
		cout<<e[i]<<" ";
	}
	puts("");
	return 0;
}

重新从基础课开始学数据结构，四个函数，初始化函数，向链表头插入一个数，删除第k个插入的数后面的数，在第k个插入的数后面插入一个数

删除第k个插入的数后面的数的时候，要特判一下是不是头节点

我们在操作的时候要把输入的k减小1，因为一般是从函数是从0开始使用，但是我们现实生活中计数是从1开始计数，和数组下标从0开始计数同理

输出链表也需要记住

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int e[N],ne[N];//节点的数值和指针
int head;
int idx;//表示有多少个结点
void init()//初始化链表
{
	head=-1;
	idx=0;
}
void add_head(int x)//向链表头插入一个数
{
	e[idx]=x;
	ne[idx]=head;
	head=idx++;
}
void remove(int k)//删除第k 个插入的数后面一个数
{
	ne[k]=ne[ne[k]];
}
void add(int k,int x)//向第k个插入的数后面插入一个数
{
	e[idx]=x;
	ne[idx]=ne[k];
	ne[k]=idx++;
}
int main()
{
	init();//初始化
	int t;
	cin>>t;
	while(t--)//多次询问
	{
		char s[10];
		cin>>s;
		if(s[0]=='H')//头节点
		{
			int x;
			cin>>x;
			add_head(x);
		}
		else if(s[0]=='D')//删除
		{
			int k;
			cin>>k;
			if(k==0)	head=ne[head];//特判头节点
			else remove(k-1);//注意计数的差异
		}
		else//插入
		{
			int k,x;
			cin>>k>>x;
			add(k-1,x);
		}
	}
	for(int i=head;i!=-1;i=ne[i])//输出链表
	{
		cout<<e[i]<<" ";
	}
	puts("");
	return 0;
}