Java 单链表
使用结构体、类形成的链表是会TLE的,因此我们需要使用一个快速增删查节点的方法。
我们都知道数组的查询速度是最快的,我们可以尝试使用数组模拟链表实现快速增删查节点的目的。
我们可以使用两个数组保存每个节点当前的值与下一个节点的指针域,下标为两个数组的联系,同时下标其实也起到了记录节点插入时间顺序的目的(对应本题).
另外使用两个变量 index
保存当前可可插入的数组下标、head
保存头节点的数组下标
但也可以使用下标0的位置充当头节点,可以省去实现从链表头插入元素的方法
import java.util.*;
import java.io.*;
public class Main{
//快读快写
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
public static int nextInt() throws IOException{
in.nextToken();
return (int) in.nval;
}
public static String nextLine() throws IOException {
in.nextToken();
return in.sval;
}
static int N = (int) 1e5 + 10;
static int[] val = new int[N];
static int[] next = new int[N];
static int index;
public static void main(String[] args) throws IOException{
int m = nextInt();
//初始化链表
init();
while(m --> 0){
String choose = nextLine();
int x;
int k = 0;
if("H".equals(choose)){
x = nextInt();
insert(k, x);
}
else if("D".equals(choose)){
k = nextInt();
delete(k);
}
else {
k = nextInt();
x = nextInt();
insert(k, x);
}
}
int temp = next[0];
while(temp != -1){
pr.print(val[temp] + " ");
temp = next[temp];
}
pr.flush();
}
public static void init(){
index = 0;
val[index] = 0;
next[index ++ ] = -1;
}
public static void delete(int k){
next[k] = next[next[k]];
}
public static void insert(int k, int x){
val[index] = x;
next[index] = next[k];
next[k] = index ++;
}
}