AcWing 827. 双链表-JAVA(注释)
原题链接
简单
作者:
鼠鼠我
,
2021-01-28 23:11:34
,
所有人可见
,
阅读 308
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 100010;
static int[] e;
static int[] r;
static int[] l;
static int idx;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
e = new int[N];
r = new int[N];
l = new int[N];
init();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s[] = br.readLine().split("\\s+");
int m = Integer.parseInt(s[0]);
while(m-- >0)
{
String ss[] = br.readLine().split("\\s+");
if(ss[0].equals("L"))
{
int x = Integer.parseInt(ss[1]);
add(0, x);
}
else if(ss[0].equals("R"))
{
int x = Integer.parseInt(ss[1]);
add(l[1], x);
}
else if(ss[0].equals("D"))
{
int x = Integer.parseInt(ss[1]);
remove(x+1);
}
else if(ss[0].equals("IL"))
{
int k = Integer.parseInt(ss[1]);
int x = Integer.parseInt(ss[2]);
add(l[k+1], x);//下标从0开始
}
else if(ss[0].equals("IR"))
{
int k = Integer.parseInt(ss[1]);
int x = Integer.parseInt(ss[2]);
add(k+1, x);//下标从0开始
}
}
for(int i=r[0];i!=1;i=r[i])
{
System.out.print(e[i]+" ");
}
}
static void init()//初始化
{
r[0] = 1;//首先定义0的右边是1,0是双链表的开头
l[1] = 0;//1的左边是0
idx = 2;//因为已经有两了,所以idx从2开始
}
static void add(int k,int x)//在下标为k的右边插入x
{
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;//先写右边指向现在的点==idx,否则下面的代码就会更改
r[k] = idx;
idx++;
}
static void remove(int k)//删除第k个点
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
}