AcWing 827. 双链表
原题链接
简单
import java.util.Objects;
import java.util.Scanner;
public class Main {
private static final int N = 100010;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int m = in.nextInt();
MyDoubleLinkedList myDoubleLinkedList = new MyDoubleLinkedList();
while (m-- > 0) {
String op = in.next();
if (Objects.equals(op, "L")) {
int x = in.nextInt();
myDoubleLinkedList.insert(0, x);
} else if (Objects.equals(op, "R")) {
int x = in.nextInt();
myDoubleLinkedList.insert(myDoubleLinkedList.getLeft(1), x);
} else if (Objects.equals(op, "D")) {
int k = in.nextInt();
myDoubleLinkedList.remove(k + 1);
} else if (Objects.equals(op, "IL")) {
int k = in.nextInt();
int x = in.nextInt();
myDoubleLinkedList.insert(myDoubleLinkedList.getLeft(k + 1), x);
} else if (Objects.equals(op, "IR")) {
int k = in.nextInt();
int x = in.nextInt();
myDoubleLinkedList.insert(k + 1, x);
}
}
myDoubleLinkedList.print();
}
private static class MyDoubleLinkedList {
private static final int[] val = new int[N];
private static final int[] left = new int[N];
private static final int[] right = new int[N];
private static int index;
/**
* 初始化双链表
*/
public MyDoubleLinkedList() {
// left和right作为起点和终点
left[1] = 0;
right[0] = 1;
index = 2;
}
/**
* 插入k 位置的左边
*
* @param k 位置
* @param x 插入的值
*/
private void insert(int k, int x) {
// 将插入的值x赋值给idx位置的数组val
val[index] = x;
// 维护双链表左索引
left[index] = k;
// 维护双链表右索引(原来k位置的右索引)
right[index] = right[k];
// 维护原来k位置的右索引的左索引
left[right[k]] = index;//先做这一步
// 维护原来k位置的右索引
right[k] = index;
index++;
}
/**
* 删除
*
* @param k 位置
*/
private void remove(int k) {
left[right[k]] = left[k];// 将k位置的右索引的左索引,指向k的左索引
right[left[k]] = right[k];// 将k位置的左索引的右索引,指向k的右索引
}
private void print() {
for (int i = right[0]; i != 1; i = right[i]) {
System.out.print(val[i] + " ");
}
}
private Integer getLeft(int k) {
return left[k];
}
}
}