数组模拟单链表

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

向链表头插入一个数;
删除第 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)。
输出格式
共一行,将整个链表从头到尾输出。

import java.util.*;
import java.io.*;

public class Main {
	static int INF = 0x3f3f3f3f;
	static int MOD = 998244353;
	static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
	static int n;
	static int N = 100010;
	static int head = -1;
	static int e[] = new int [N];
	static int ne[] = new int [N];
	static int idx = 1;
	static void add_to_head(int x) {
		e[idx] = x; ne[idx] = head; head = idx ++;
		}
	
	static void add_to_k(int k ,int x) {
		e[idx] = x; ne[idx] = ne[k]; ne[k] = idx; idx ++;
	}
	
	static void remove(int k) {
		ne[k] = ne[ne[k]];
	}
    public static void main(String[] args) throws IOException {
    	Scanner sc = new Scanner(System.in);
    	n = sc.nextInt();
    	while(n --> 0) {
    		char s = sc.next().charAt(0);
    		if(s == 'H') {
    			int x = sc.nextInt();
    			add_to_head(x);
    		}else if(s == 'D') {
    			int k = sc.nextInt();
    			if(k == 0) head = ne[head];
    			else remove(k);
    		}else {
    			int k = sc.nextInt();
    			int x = sc.nextInt();
    			add_to_k(k, x);
    		}
    	}
    	
    	for(int i = head; i != -1; i = ne[i] ) {
    		System.out.println(e[i]);
    	}
    	sc.close();
    	pw.close();
    }
}


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

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

相关文章

全网最详细,Jmeter性能测试数据写入文件(总结)看这篇就够了......

目录:导读前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结(尾部小惊喜)前言 jmeter 性能测试数据…

RK3568平台开发系列讲解(Linux系统篇)消息队列

🚀返回专栏总目录 文章目录 一、创建消息队列二、发送和接收消息三、内核结构沉淀、分享、成长,让自己和他人都能有所收获!😄 📢消息队列在如下两个方面上比管道有所增强: 消息队列中的数据是有边界的,发送端和接收端能以消息为单位进行交流,而不再是无分隔的字节流…

Android---动态权限申请

目录 权限分类 动态权限核心函数 简易实现案例 完整代码 Google 在 Android 6.0 开始引入了权限申请机制,将所有权限分成了正常权限和危险权限。App 每次在使用危险权限时需要动态的申请并得到用户的授权才能使用。 权限分类 系统权限分为两类:正常…

队列实现及leetcode相关OJ题

上一篇写的是栈这一篇分享队列实现及其与队列相关OJ题 文章目录一、队列概念及实现二、队列源码三、leetcode相关OJ一、队列概念及实现 1、队列概念 队列同栈一样也是一种特殊的数据结构,遵循先进先出的原则,例如:想象在独木桥上走着的人&am…

计算机网络管理 TCP三次握手的建立过程,Wireshark抓包分析并验证TCP三次握手建立连接的报文

⬜⬜⬜ ---🟧🟨🟩🟦🟪 (*^▽^*)欢迎光临 🟧🟨🟩🟦🟪---⬜⬜⬜ ✏️write in front✏️ 📝个人主页:陈丹宇jmu 🎁欢迎各位→…

【Linux入门篇】操作系统安装、网络配置

目录 🍁Linux详解 🍂1.操作系统 🍂2.操作系统组成 🍂3.操作系统历史 🍂4.常见的Linux系统 🍂5.centos7下载 🍂6.安装centos7 🍁linux初始化配置 🍃1.虚拟机系统安装后操作…

从零实现深度学习框架——学习率调整策略介绍

引言 本着“凡我不能创造的,我就不能理解”的思想,本系列文章会基于纯Python以及NumPy从零创建自己的深度学习框架,该框架类似PyTorch能实现自动求导。 要深入理解深度学习,从零开始创建的经验非常重要,从自己可以理解的角度出发,尽量不使用外部完备的框架前提下,实现我…

【微信小程序】-- 案例 - 自定义 tabBar(四十六)

💌 所属专栏:【微信小程序开发教程】 😀 作  者:我是夜阑的狗🐶 🚀 个人简介:一个正在努力学技术的CV工程师,专注基础和实战分享 ,欢迎咨询! &…

kali内置超好用的代理工具proxychains

作者:Eason_LYC 悲观者预言失败,十言九中。 乐观者创造奇迹,一次即可。 一个人的价值,在于他所拥有的。所以可以不学无术,但不能一无所有! 技术领域:WEB安全、网络攻防 关注WEB安全、网络攻防。…

31. 下一个排列

题目链接:https://leetcode.cn/problems/next-permutation/解题思路:整数数组的 下一个排列 是指其整数的下一个字典序更大的排列,其实也就是把整数所有数字从左往右组合成一个数,则下一个排列就是将数组中的所有元素重新组合成一…

【跟着chatgpt学go】Gooutine和Channel

Goroutine Goroutine 是 Go 语言中的一种并发机制,它是一种轻量级线程,可以通过关键字 go 启动一个新的 Goroutine。相比传统的线程,Goroutine 拥有更小的栈空间,因此可以创建更多的 Goroutine。 下面是一个简单的 Goroutine 的…

数据结构初阶(顺序表)

文章目录1、时间复杂度1.2、大O渐进表示法1.3、递归算法时间复杂度计算2、空间复杂度3、顺序表1、概念2、静态顺序表3、动态顺序表1、创建结构体(头文件中创建)2、销毁链表3、初始化结构体4、打印函数5、内存扩容6、顺序表任意位置插入数据7、顺序表任意…

从 hybrid开发----》微前端

为什么开始写关于微前端的一系列博客? 1. 学生时代讨论关于hybrid APP的应用开发,历史的选择总是变化的,需要更进一步深入。 2. 之前工作项目中见到过沙箱隔离之后CSS冲突,需要学一下如何解决 ----------------------------- …

QT CTK插件框架 (一 下载编译)

CTK 为支持生物医学图像计算的公共开发包,其全称为 Common Toolkit。为医学成像提供一组统一的基本功能;促进代码和数据的交互及结合;避免重复开发;在工具包(医学成像)范围内不断扩展到新任务,而…

ChatGPT助力校招----面试问题分享(四)

1 ChatGPT每日一题:电阻如何选型 问题:电阻如何选型 ChatGPT:电阻的选型通常需要考虑以下几个方面: 额定功率:电阻的额定功率是指电阻能够承受的最大功率。在选型时,需要根据电路中所需要的功率确定所选…

【JavaEE】Thread 类及常用方法

一、Thread 类Thread 类我们可以理解为是 java 用于管理线程的一个类,里面封装了操作系统提供的线程管理这一方面的 API (Thread 是优化后的结果), Java 代码创建的每一个线程,可以理解为为 Thread 实例化的对象,Threa…

JUC是什么?

JUC 简介 在 Java 中,线程部分是一个重点,本篇文章说的 JUC 也是关于线程的。JUC 就是 java.util .concurrent 工具包的简称。这是一个处理线程的工具包,JDK 1.5 开始出现的。 进程与线程 进程(Process) 是计算机中…

Java基础:笔试题

文章目录Java 基础题目1. 如下代码输出什么?2. 当输入为2的时候返回值是多少?3. 如下代码输出值为多少?4. 给出一个排序好的数组:{1,2,2,3,4,5,6,7,8,9} 和一个数,求数组中连续元素的和等于所给数的子数组解析第一题第二题第三题第四题方案…

[ 云计算 | Azure ] Chapter 05 | 核心体系结构之管理组、订阅、资源和资源组以及层次关系

本文主要对如下内容进行讲解:Azure云计算的核心体系结构组件中的:资源、订阅和资源组,以及了解 Azure 资源管理器 (ARM) 如何部署资源。 本系列已经更新文章列表: [ 云计算 | Azure ] Chapter 03 | 描述云计算运营中的 CapEx 与…

面试了8家软件公司测试岗位,面试题大盘点,我真的尽力了

包含的模块:本文分为十九个模块,分别是:软件测试 基础、liunx、MySQL、web测试、接口测试、APP测试 、管理工具、Python、性能测试、selenium、lordrunner、计算机网络、组成原理、数据结构与算法、逻辑题、人力资源需要的可以看文末获取方式…
最新文章