单链表(Java每日一题)
JAVA 每日 单链
2023-09-14 09:14:24 时间
单链表
实现一个单链表,链表初始为空,支持三种操作:
向链表头插入一个数;
删除第 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
C++
#include<iostream>
using namespace std;
const int N = 100010;
// head 表示头节点
// e[i] 表示结点i的值
// ne[i] 表示结点i的next指针是多少
// idx 存储当前已经用到了的那个点
// 在这里面要记住的是idx 和 ne[]都是指针
int head, e[N], ne[N], idx;
// 初始化
void init()
{
head = -1;
idx = 0;
}
void add_to_head(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
void add(int k, int x)
{
e[idx] = x; // e[idx]是一个新的结点
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
void remove(int k)
{
if (k == -1) head = ne[head];
else ne[k] = ne[ne[k]];
}
int main()
{
int m;
cin >> m;
init();
while (m--)
{
int k, x;
char op;
cin >> op;
if (op == 'H')
{
cin >> x;
add_to_head(x);
}
else if (op == 'D')
{
cin >> k;
remove(k - 1);
}
else
{
cin >> k >> x;
add(k - 1, x);
}
}
for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
cout << endl;
return 0;
}
Java
import java.io.*;
public class Main
{
static int n;
static int k, x;
static int head;
static int idx;
static int N = 100010;
static int[] e = new int[N], ne = new int[N];
public static void init()
{
idx = 0;
head = -1;
}
public static void addToHead(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx;
idx ++;
}
public static void remove(int k)
{
ne[k] = ne[ne[k]];
}
public static void insert(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx ++;
}
public static void main(String[] args) throws IOException
{
init();
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(reader.readLine());
while(n -- != 0)
{
String [] s = reader.readLine().split(" ");
if (s[0].equals("H"))
{
x = Integer.parseInt(s[1]);
addToHead(x);
}
else if (s[0].equals("D"))
{
k = Integer.parseInt(s[1]);
if (k == 0) head = ne[head];
else remove(k - 1);
}
else
{
k = Integer.parseInt(s[1]);
x = Integer.parseInt(s[2]);
insert(k - 1, x);
}
}
for (int i = head; i != -1; i = ne[i])
{
System.out.print(e[i] + " ");
}
}
}
相关文章
- java标识符与关键字_4、Java标识符和关键字
- java启动器_JAVA基础:Java 启动器如何查找类
- JAVA 实现简单的学生成绩管理系统
- java冒泡排序代码_Java冒泡排序
- java笛卡尔积算法_Java 笛卡尔积算法的简单实现
- java 常量表达式,需要常量表达式? (Java switch语句)[通俗易懂]
- 大数据必学Java基础(一百一十一):过滤器注解应用和开发案例
- Java 递归列出目录下的文件以及子目录详解编程语言
- 利用Java来压缩 JavaScript 代码详解编程语言
- Java中BIO和NIO详解编程语言
- 写入数据Java实现MySQL数据写入(java向mysql)
- 数据库轻松搞定:用Java访问Oracle数据库(java访问oracle)
- 数据挖掘Redis中Java过期数据的威力(redisjava过期)
- 时间如何正确设置Redis中Java客户端的过期时间(redisjava过期)
- 数据解决Redis中Java数据过期问题(redisjava过期)
- Java与Linux:前景迷人的新科技(java和linux前景)
- Java配置Oracle实现稳定的跨平台数据库连接(java配置oracle)
- Oracle数据库中运行Java程序的简易指南(oracle中写java)
- Java中的观察者模式实例讲解