【826. 单链表】

单链表
实现一个单链表,链表初始为空,支持三种操作:

向链表头插入一个数;
删除第 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

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

//head表示头结点的下标
//e[i]表示下表i的值
//ne[i]表示下标i的next指针是多少
//idx 表示当前用到了哪个点
int head, e[N], ne[N],idx;

void init()
{
  head = -1;
  idx = 0;
}

//在头结点后插入一个节点x
void add_head(int x)
{
  e[idx] = x, ne[idx] = head, head = idx, idx++;
}
//将x插入到下标是k的点的后面
void add(int k, int x)
{
  e[idx] = x, ne[idx] = ne[k], ne[k] = idx, idx++;
}
//将下标是k的后面的点删除
void remove(int k)
{
  ne[k] = ne[ne[k]];
}

int main()
{
  int m;
  cin >> m;
  init ();
  while(m--)
  {
    char op;
    int k,x;
    cin >> op;
    if(op == 'H')
    {
      cin >> x;
      add_head(x);
    }
    else if(op == 'I')
    {
      cin >> k >> x;
      add(k - 1, x);
    }
    else
    {
      cin >> k;
      if(!k) head = ne[head];//如果k为0时删除头结点
      remove(k - 1);
    }
  }
  
  for(int i = head; i!= -1; i = ne[i]) cout << e[i] << ' ';
  cout << endl;
  return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/92494.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Git gui教程---第七篇 Git gui的使用 返回上一次提交

1&#xff0e; 查看历史&#xff0c;打开gitk程序 2&#xff0e; 选中需要返回的版本&#xff0c;右键&#xff0c;然后点击Rest master branch to here 3.出现弹窗 每个选项我们都试一下&#xff0c;从Hard开始 返回的选项 HardMixedSoft Hard 会丢失所有的修改【此处的…

【Jellyfin影音服务器】 本地部署公网远程影音库

文章目录 1. 前言2. Jellyfin服务网站搭建2.1. Jellyfin下载和安装2.2. Jellyfin网页测试 3.本地网页发布3.1 cpolar的安装和注册3.2 Cpolar云端设置3.3 Cpolar本地设置 4.公网访问测试5. 结语 1. 前言 随着移动智能设备的普及&#xff0c;各种各样的使用需求也被开发出来&…

dig批量域名逆向查询ip

dig批量域名逆向查询ip dig nocmd noall answer -f iplist.txtiplist.txt中内容 效果图&#xff1a; dig其他选项参数&#xff1a; dig www.baidu.com A # 查询A记录&#xff0c;如果域名后面不加任何参数&#xff0c;默认查询A记录 dig www.baidu.com MX # 查询MX记…

重新认识Android中的线程

线程的几种创建方式 new Thread&#xff1a;可复写Thread#run方法。也可以传递Runnable对象&#xff0c;更加灵活。缺点&#xff1a;缺乏统一管理&#xff0c;可能无限制新建线程&#xff0c;相互之间竞争&#xff0c;及可能占用过多系统的资源导致死机或oom。 new Thread(new…

LeetCode-406-根据身高重建队列

题目描述&#xff1a; 假设有打乱顺序的一群人站成一个队列&#xff0c;数组 people 表示队列中一些人的属性&#xff08;不一定按顺序&#xff09;。每个 people[i] [hi, ki] 表示第 i 个人的身高为 hi &#xff0c;前面 正好 有 ki 个身高大于或等于 hi 的人。 请你重新构造…

VB.NET调用VB6 Activex EXE实现PowerBasic和FreeBasic的标准DLL调用

VB6写的ActiveX EXE公共对象是外置进程&#xff0c;因此&#xff0c;尽管它是x86 32位的进程&#xff0c;但可以集成到 VB.NET的x64和x32程序中使用。 VS2022的VB.NET程序&#xff0c;调用ActiveX DLL对象我在上篇笔记中写了 VB.NET通过VB6 ActiveX DLL调用PowerBasic及FreeB…

Git向远程仓库与推送以及拉取远程仓库

理解分布式版本控制系统 1.中央服务器 我们⽬前所说的所有内容&#xff08;⼯作区&#xff0c;暂存区&#xff0c;版本库等等&#xff09;&#xff0c;都是在本地也就是在你的笔记本或者计算机上。⽽我们的 Git 其实是分布式版本控制系统&#xff01;什么意思呢? 那我们多人…

计算机网络(10) --- 高级IO

计算机网络&#xff08;9&#xff09; --- 数据链路层与MAC帧_哈里沃克的博客-CSDN博客数据链路层与MAC帧https://blog.csdn.net/m0_63488627/article/details/132178583?spm1001.2014.3001.5501 目录 1.IO介绍 1.IO本质 2.IO模型 2.非阻塞 3.IO多路转接 1.select 编写…

电阻器件的分类

电阻器的种类碳膜电阻膜式电阻器中的一种。气态碳氢化合物在高温和真空中分解&#xff0c;碳沉积在瓷棒或者瓷管上&#xff0c;形成一层结晶碳膜。改变碳膜厚度和用刻槽的方式变更碳膜的长度可以得到不同的阻值。碳膜电阻成本较低&#xff0c;电性能和稳定性较差&#xff0c;一…

Python自动化小技巧21——实现PDF转word功能(程序制作)

案例背景 为什么这个年代PDF转word&#xff0c;某wps居然还要收费.....很多软件都可以实现这个功能&#xff0c;但是效果都有好有坏&#xff0c;而且有的还付费&#xff0c;很麻烦。 那就用python实现这个功能吧&#xff0c;然后把代码打包为.exe的程序&#xff0c;这样随便在…

企业网络日志安全与 EventLog Analyzer

企业的网络日志安全是一项至关重要的任务。随着信息技术的迅猛发展&#xff0c;网络攻击和数据泄露的威胁也与日俱增。为了应对这些威胁&#xff0c;企业需要强大的工具来监控、分析和保护其网络日志。而ManageEngine的EventLog Analyzer正是这样一款卓越的解决方案。 网络日志…

Sentinel 控制台(集群流控管理)

规则配置 要通过 Sentinel 控制台配置集群流控规则&#xff0c;需要对控制台进行改造。我们提供了相应的接口进行适配。 从 Sentinel 1.4.0 开始&#xff0c;我们抽取出了接口用于向远程配置中心推送规则以及拉取规则&#xff1a; DynamicRuleProvider<T>: 拉取规则Dy…

网站和API支持HTTPS,最好在Nginx上配置

随着我们网站用户的增多&#xff0c;我们会逐渐意识到HTTPS加密的重要性。在不修改现有代码的情况下&#xff0c;要从HTTP升级到HTTPS&#xff0c;让Nginx支持HTTPS是个很好的选择。今天我们来讲下如何从Nginx入手&#xff0c;从HTTP升级到HTTPS&#xff0c;同时支持静态网站和…

Spark Standalone环境搭建及测试

&#x1f947;&#x1f947;【大数据学习记录篇】-持续更新中~&#x1f947;&#x1f947; 篇一&#xff1a;Linux系统下配置java环境 篇二&#xff1a;hadoop伪分布式搭建&#xff08;超详细&#xff09; 篇三&#xff1a;hadoop完全分布式集群搭建&#xff08;超详细&#xf…

神经网络学习小记录75——Keras设置随机种子Seed来保证训练结果唯一

神经网络学习小记录75——Keras设置随机种子Seed来保证训练结果唯一 学习前言为什么每次训练结果不同什么是随机种子训练中设置随机种子 学习前言 好多同学每次训练结果不同&#xff0c;最大的指标可能会差到3-4%这样&#xff0c;这是因为随机种子没有设定导致的&#xff0c;我…

Unity3D软件安装包分享(附安装教程)

目录 一、软件简介 二、软件下载 一、软件简介 Unity3D是一款全球知名的游戏开发引擎&#xff0c;由Unity Technologies公司开发。它提供了一个跨平台、多功能的开发环境&#xff0c;支持创建2D和3D游戏、交互式应用、虚拟现实、增强现实等多种类型的应用程序。以下是Unity3D…

CFC编程入门_【10分钟学会】

什么是CFC&#xff1a; 【差不多10分钟全学会】 CFC是图形化编程&#xff0c; 跟单片机的连线一样&#xff0c; 唯一的区别&#xff1a;功能块右侧是【只能输出】引脚。 只有左侧引脚可以输入输出。 有哪些控件&#xff1a; 指针&#xff1a;用于拖动功能块。 控制点&#xf…

VR全景:助力乡村振兴,实现可持续发展

引言&#xff1a; 随着科技的飞速发展&#xff0c;虚拟现实&#xff08;VR&#xff09;全景技术正在以惊人的速度改变着我们的生活方式和产业格局。全景技术不仅在娱乐、教育等领域取得了巨大成功&#xff0c;也为乡村振兴提供了全新的机遇。通过以乡村为背景的VR全景体验&…

【Linux】以太网协议以及MTU

以太网协议 数据链路层的功能以太网的数据格式MTUMTU对IP协议的影响MTU对UDP协议的影响MTU对TCP协议的影响 数据链路层的功能 数据链路层的主要功能是&#xff1a;控制链路。包括数据链路的建立、链路的维护和释放。MAC寻址也是它的功能&#xff0c;寻址是指计算机网卡的MAC地…

数据结构(Java实现)-包装类和泛型

包装类 在Java中&#xff0c;由于基本类型不是继承自Object&#xff0c;为了在泛型代码中可以支持基本类型&#xff0c;Java给每个基本类型都对应了 一个包装类型。 基本数据类型和对应的包装类 装箱和拆箱 装箱操作&#xff0c;新建一个 Integer 类型对象&#xff0c;将 i 的…
最新文章