AcWing 826. 单链表
原题链接
简单
作者:
domiso
,
2021-08-26 15:12:57
,
所有人可见
,
阅读 174
import java.util.*;
import java.io.*;
public class Main{
private static int[] nv = new int[100010];//node.val
private static int[] nt = new int[100010];//node.next
private static int head;//头节点指针
private static int idx;//第多少个节点
private static void init (){//初始化
head = - 1;//空节点
idx = 1;//没有存储数据,从1开始方便后面插入到第k个节点,直接传入k就行,不需要传入k - 1;模拟了该节点的地址
}
private static void addFirst(int x){//头插法
nv[idx] = x; //newNode.val = x;
nt[idx] = head; //newNode.next = head;
head = idx; //head = newNode;
idx ++;//开辟下一块节点地址
}
private static void add(int k , int x){//插入到第k个节点后面
nv[idx] = x; //newNode.val = x;
nt[idx] = nt[k]; // newNode.next = nodek.next
nt[k] = idx; //nodek.next = newNode;
idx ++;//开辟下一块节点地址
}
private static void del(int k) {
//删除第k个节点
if(k == 0) head = nt[head];//注意题意是k = 0时为删除头节点
nt[k] = nt[nt[k]];//k.next -> k.next.next
}
public static void main (String[] args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));//buffer比scanner快
int m = Integer.parseInt(in.readLine());//处理输入
init();//初始化
while(m -- > 0) {
String[] s = in.readLine().split(" ");//处理输入
int k = Integer.parseInt(s[1]);
if(s[0].equals("H")) {//头插法
addFirst(k);
}else if(s[0].equals("I")) {//插入到第k个节点后面
add(k,Integer.parseInt(s[2]));
}else{//删除某一节点
del(k);
}
}
for(int i = head;i != -1;i = nt[i]) {
System.out.print(nv[i] + " ");
}
}
}