题目描述
实现一个单链表,链表初始为空,支持三种操作:
向链表头插入一个数;
删除第 k 个插入的数后面的数;
在第 k 个插入的数后插入一个数。
现在要对该链表进行 M 次操作,进行完所有操作后,从头到尾输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数,则按照插入的时间顺序,这 n 个数依次为:第 1 个插入的数,第 2 个插入的数,…第 n 个插入的数。
输入格式
第一行包含整数 M,表示操作次数。
接下来 M 行,每行包含一个操作命令,操作命令可能为以下几种:
H x,表示向链表头插入一个数 x。
D k,表示删除第 k 个插入的数后面的数(当 k 为 0 时,表示删除头结点)。
I k x,表示在第 k 个插入的数后面插入一个数 x(此操作中 k 均大于 0)。
输出格式
共一行,将整个链表从头到尾输出。
数据范围
1≤M≤100000
所有操作保证合法。
输入样例:
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
输出样例:
6 4 6 5
样例
// 本人菜鸟,没有系统学过数据结构,基础不牢啊属于是==
// 一个单链表可能没有头节点,但不能没有头指针
// 头结点的数据域可以不存放任何数据
// 按照y总的话来说,一个结点包括该点的值和指向下一个元素的指针
#include<iostream> // 链表有带头节点的和不带头节点的,数据结构得去补补课了,还有节点和结点的区别
using namespace std;
const int N=1e5+10;
int head=-1,idx=0; // 为什么是-1? 答:刚开始指向空节点,表示没有null内容,在链表里有元素的时候,指向第一个元素,为什么是0?表示从0号位置开始
int e[N],ne[N],n; // e[N]存储数据,ne[N]存储下一个元素的指针
// idx 表示当前操作的数
void H(int x) // 其实我觉得y总这儿没讲清楚,今天重刷的时候再读一遍题目,“在链表头插入一个数”,而实际是在链表头和第一个数之间插入。
{
e[idx]=x; // 将插入的x 的值放入存的数组中
ne[idx]=head; // 将头节点的值给存入下一个元素的指针
head=idx++; // 将临时的值传给头节点
}
void D(int k)
{
ne[k]=ne[ne[k]]; // 让k的指针指向k的下下一个人,跳过k的下一个人,这样k就被挤掉了
}
void I(int k,int x) // 实际是插入第k个元素的后一个元素
{
e[idx]=x; // 先将元素插进去
ne[idx]=ne[k]; // 让元素配套的指针,指向它要占位的元素的下一个位置
ne[k]=idx++; // 将原来元素的指针指向自己且往后移
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) // 这里从1 开始是因为系统默认的是输入的第一个元素就是1
{
int k,x;
char s;
cin>>s;
if(s=='H')
cin>>x,H(x); // 简便做法,拿下!
else if(s=='D')
{
cin>>k; //正确理解:当头节点没有值的时候
if(k==0) head=ne[head]; //(错误理解) 如果k等于0,删除头节点,即将头节点的下一个指向返还给head (可能不对,但这样好记忆)
else D(k-1); // 题目说删除的是第k个元素,实际上按题目的意思是从1 开始,但我们的下标是从0开始,那就是删除下表为第k-1的数
}
else
cin>>k>>x,I(k-1,x);
} // 一整个for循环中遍历输入的s的表示,再判断增删
for(int i=head;i!=-1;i=ne[i]) // 这里的i和上一个for循环的i 应该是有关系,不然为什么说往后走一个呢?
// 但又觉得i不是局部变量吗,上下怎么会有关系呢? 看了很多人的题解,都没有说这个问题,大家怎么理解的?还是直接忽略了?
// 从head 为-1开始遍历,当i不再等于-1时,表示遍历到空结点循环终止,i往后走一个
cout<<e[i]<<' ';
return 0;
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla