AcWing 826. 单链表
原题链接
简单
作者:
microboat
,
2024-03-15 11:11:56
,
所有人可见
,
阅读 8
import java.io.*;
public class Main {
static int N = 100010;
static int[] e, ne;
static int head, idx;
// 初始化:e 存储当前节点的数,ne 存储当前节点指向下个节点的位置
// head 默认在 -1,idx 从 0 开始分发
public static void init() {
e = new int[N];
ne = new int[N];
head = -1;
idx = 0;
}
// 插入 x 到头节点
public static void addToHead(int x) {
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
// 移除下标为 k 的数
public static void remove(int k) {
ne[k] = ne[ne[k]];
}
// 在下标为 k 地址后插入一个数 x
public static void add(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 br = new BufferedReader(new InputStreamReader(System.in));
int m = Integer.parseInt(br.readLine());
while (m-- > 0) {
String[] line = br.readLine().split(" ");
String op = line[0];
int k, x;
if (op.equals("H")) {
x = Integer.parseInt(line[1]);
addToHead(x);
} else if (op.equals("D")) {
k = Integer.parseInt(line[1]);
// k == 0 表示删除头结点,也即 head 指向 ne[head]
if (k == 0) {
head = ne[head];
} else {
remove(k - 1);
}
} else {
k = Integer.parseInt(line[1]);
x = Integer.parseInt(line[2]);
add(k - 1, x);
}
}
for (int i = head; i != -1; i = ne[i]) {
System.out.print(e[i] + " ");
}
}
}