AcWing 826. 单链表
原题链接
简单
import java.util.Arrays;
import java.util.Scanner;
public class Main {
private static final int N = 100010;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
MySingleLinkedList mySingleLinkedList = new MySingleLinkedList();
int m = in.nextInt();
while (m-- > 0) {
String sa = in.next();
char op = sa.charAt(0);
if (op == 'H') {
int x = in.nextInt();
mySingleLinkedList.addHead(x);
} else if (op == 'D') {
int k = in.nextInt();
if (k == 0) {
mySingleLinkedList.removeHead();
} else {
mySingleLinkedList.remove(k - 1);
}
} else if (op == 'I') {
int k = in.nextInt();
int x = in.nextInt();
mySingleLinkedList.add(k - 1, x);
} else {
throw new RuntimeException();
}
}
mySingleLinkedList.print();
}
private static class MySingleLinkedList {
private static int head;//头节点
private static final int[] val = new int[N]; //值
private static final int[] next = new int[N]; //类比next指针
private static int index; //当前用了多少个点
/**
* 初始化单链表
*/
public MySingleLinkedList() {
head = -1;
index = 0;
Arrays.fill(next, -1);
}
/**
* 插入头节点
*
* @param x 插入的值
*/
private void addHead(int x) {
// 将插入的值x赋值给idx位置的数组val
val[index] = x;
// 将原来的head赋值给idx位置的数组next
next[index] = head;
// 将idx位置赋值给head,然后idx++
head = index++;
}
/**
* 插入
*
* @param k 位置
* @param x 插入的值
*/
private void add(int k, int x) {
// 将插入的值x赋值给idx位置的数组val
val[index] = x;
// 将原来的next[k]赋值给idx位置的数组next
next[index] = next[k];
// 将idx位置赋值给next[k],然后idx++
next[k] = index++;
}
/**
* 删除头节点
*/
private void removeHead() {
// 将原来的next[head]赋值给head,头节点指向原来头节点的下一位
head = next[head];
}
/**
* 删除
*
* @param k 位置
*/
private void remove(int k) {
// 将原来的next[k]的next赋值给next[k],k位置的下一位指向k位置的下一位的下一位
next[k] = next[next[k]];
}
/**
* 输出
*/
private void print() {
// 从头结点开始遍历,如果当前位置不是-1,则继续遍历next[i]
for (int i = head; i != -1; i = next[i]) {
System.out.print(val[i] + " ");
}
}
}
}