AcWing 827. 双链表
原题链接
简单
作者:
microboat
,
2024-03-15 11:37:05
,
所有人可见
,
阅读 9
import java.io.*;
public class Main {
static int N = 100010;
static int[] e, l, r;
static int idx;
public static void init() {
e = new int[N];
l = new int[N];
r = new int[N];
r[0] = 1;
l[1] = 0;
idx = 2;
}
// 默认在 k 的右侧插入 x
public static void add(int k, int x) {
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
idx++;
}
// 移除下标为 k 的数
public static void remove(int k) {
r[l[k]] = r[k];
l[r[k]] = l[k];
}
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("L")) {
x = Integer.parseInt(line[1]);
// 最左侧,就是头节点的右侧
add(0, x);
} else if (op.equals("R")) {
// 最右侧,就是尾节点左侧的右侧
x = Integer.parseInt(line[1]);
add(l[1], x);
} else if (op.equals("D")) {
// idx 从 2 开始,第 k 位就是 下标为 k + 1
k = Integer.parseInt(line[1]);
remove(k + 1);
} else if (op.equals("IL")) {
// k 的左侧,就是 在下标为 k + 1 的左侧的右侧
k = Integer.parseInt(line[1]);
x = Integer.parseInt(line[2]);
add(l[k + 1], x);
} else {
// k 的右侧,就是 在下标为 k + 1 的右侧
k = Integer.parseInt(line[1]);
x = Integer.parseInt(line[2]);
add(k + 1, x);
}
}
for (int i = r[0]; i != 1; i = r[i]) {
System.out.print(e[i] + " ");
}
}
}