AcWing 826. 单链表
原题链接
简单
作者:
dameng
,
2023-03-05 11:20:57
,
所有人可见
,
阅读 134
模拟单链表
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine());
Linkedlist list = new Linkedlist(n);
for (int i = 0; i < n; i ++ ) {
String str = sc.nextLine();
// System.out.println("str:" + str);
String[] strs = str.split(" ");
if ("H".equals(strs[0])) {
int x = Integer.parseInt(strs[1]);
list.add(x);
// list.printList();
} else if ("D".equals(strs[0])) {
int k = Integer.parseInt(strs[1]);
if (k == 0) list.removeHead();
else list.remove(k - 1);
// list.printList();
} else if ("I".equals(strs[0])) {
int k = Integer.parseInt(strs[1]);
int x = Integer.parseInt(strs[2]);
list.insert(k - 1, x);
// list.printList();
}
}
list.printList();
}
}
class Linkedlist {
public static int head;
public static int idx;
public static int[] e, ne;
public Linkedlist(int size) {
e = new int[size];
ne = new int[size];
idx = 0;
head = -1;
}
public void add(int x) {
e[idx] = x;
ne[idx] = head;
head = idx ++ ;
}
public void remove(int k) {
ne[k] = ne[ne[k]];
}
public void removeHead() {
head = ne[head];
}
public void insert(int k, int x) {
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx ++ ;
}
public void printList() {
for (int i = head; i != -1; i = ne[i]) {
System.out.print(e[i] + " ");
}
}
}