AcWing 827. 双链表--Java
原题链接
简单
作者:
domiso
,
2021-08-26 17:51:02
,
所有人可见
,
阅读 198
import java.util.*;
import java.io.*;
public class Main{
private static int N = 100010;
private static int[] e = new int[N];//node.val
private static int[] l = new int[N];//node.prev
private static int[] r = new int[N];//node.next
//数组下标0 位置存head指针 1位置存tail指针
private static int hd = 0;//head
private static int tl = 1;//tail
private static int idx;
private static void init(){
r[hd] = tl;
l[tl] = hd;
idx = 2; //后面传入k + 1 就代表是第k个节点 当k = 1 时 idx = k + 1 = 2
}
private static void add(int k , int x ) {//在第k个节点后面插入x
e[idx] = x;//newNode.val
l[idx] = k;
r[idx] = r[k];
l[r[k]] = idx;
r[k] = idx;
idx ++;
}
private static void remove(int k) {//删除第k个节点
r[l[k]] = r[k];
l[r[k]] = l[k];
}
public static void main(String[] args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int m = Integer.parseInt(in.readLine());
init();
int k, x;
while(m-- > 0) {
String[] s = in.readLine().split(" ");
if(s[0].equals("L")) { //最左端插入数 x。
x = Integer.parseInt(s[1]);
add(0,x);
}else if(s[0].equals("R")) { //最右端插入数 x。
x = Integer.parseInt(s[1]);
add(l[1],x);
}else if(s[0].equals("D")) { // 第 k 个插入的数删除。
k = Integer.parseInt(s[1]);
remove(k + 1);
}else if(s[0].equals("IL")) { //第 k 个插入的数左侧插入一个数。
k = Integer.parseInt(s[1]); x = Integer.parseInt(s[2]);
add(l[k + 1],x);
}else { //第 k 个插入的数右侧插入一个数。
k = Integer.parseInt(s[1]); x = Integer.parseInt(s[2]);
add(k + 1,x);
}
}
for(int i = r[hd];i != 1;i = r[i]) {
System.out.print(e[i] + " ");
}
}
}