AcWing 826. 单链表
原题链接
简单
作者:
Tanice
,
2024-03-01 19:07:55
,
所有人可见
,
阅读 20
数组模拟链表–简易理解版本
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main{
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
static final int N = 100010;
static int[] e = new int[N]; // 储存元素的数组-----看成链表本体
static int[] ne = new int[N]; // 储存顺序-----------看成链表的每个节点的指针,ne[i]表示第i个节点的指针指向的节点
static int idx = 0; // 元素总边界---------数组不能直接删除,所以idx用于防止覆盖,每次插入值 idx++就行
static int head = -1; // 头部“指针”
static int m;
public static int Int(String s){return Integer.parseInt(s);}
public static void insertHead(int x){
// 向头部插入节点的过程
e[idx] = x; // 1. 创建这个节点
ne[idx] = head; // 2. 由于插入的是头部,那么这个节点的next指针应该指向原链表的头部,即head
head = idx; // 3. 头部指针应当转变为新插入的这个节点编号,即idx
idx++; // 4. 由于是插入一个值,idx必须自增1
}
public static void insert(int k, int x){
// 向下标为k的节点后插入值x
e[idx] = x; // 1. 创建这个节点
ne[idx] = ne[k]; // 2. 这个节点指向的下一个node 是 下标为k的节点指向的下一个node
ne[k] = idx; // 3. 下标为k的节点的下一个node变为本次创建的节点
idx++; // 4. 由于是插入值,idx++
}
public static void delete(int k){
ne[k] = ne[ne[k]]; // 删除直接将下标为k的节点的下一个连接到它下一个的下一个即可
}
public static void main(String[] args) throws IOException {
m = Int(in.readLine());
while(m -- > 0){
String[] s = in.readLine().split(" ");
if(s[0].equals("H")) insertHead(Int(s[1]));
else if(s[0].equals("D")){
int k = Int(s[1]);
if(k == 0) head = ne[head];
else delete(k - 1);
}
else insert(Int(s[1]) - 1, Int(s[2]));
}
for(int i = head; i != -1; i = ne[i]) out.write(e[i] + " ");
out.flush();
}
}