思路
看了下评论区的,我也觉得是将idx设为1,比较好理解
这样就相当于从数组下标为1的元素开始,然后结点数就比较好对应,写题也不用考虑k-1的情况了
java代码
import java.util.Scanner;
class Main{
static int N = 100010;
static int[] e = new int[N];
static int[] ne = new int[N];
static int head;
static int idx;
static void init(){
head = -1; //这里的-1其实只是个结束符号,如果等于这个代表遇到空指针即到尽头了。换成<=0的数都行
idx = 1;
}
//x插入到头结点
static void add_to_head(int x){
ne[idx]=head;
head = idx;
e[idx] = x;
idx++;
}
//将x插到下标为k的点后面
static void add(int k, int x){
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
//将下标是k的后面的结点删除
void remove(int k){
ne[k] = ne[ne[k]];
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
init();
while(M!=0){
String m = sc.next();
if(m.equals("H")){
int x = sc.nextInt();
add_to_head(x);
}else if(m.equals("D")){
int k =sc.nextInt();
if(k == 0) head = ne[head];
else{
remove(k);
}
}else if(m.equals("I")){
int k = sc.nextInt(),x = sc.nextInt();
add(k,x);
}
M--;
}
for (int i = head; i != -1; i = ne[i]){
System.out.print(e[i]+" ");
}
}
}
写法二(将head地址存入ne[ ]中)
上面的写法中,我们只是让head表示了指针,但我觉得把指针都放在ne[]中会不会更舒服一点
具体在初始化中实现:
将head初始化为0,使head只是存头结点指针的下标,然后我们将ne[head] = -1,这样空指针也表示出来了。
再然后我们在最后循环判断的时候,只需要判断ne[i]中的指针是不是-1,即是否走到链表结束。
同理,-1只是表示链表空指针,更换成其他的数字也行!
完整代码
import java.util.Scanner;
class Main{
static int N = 100010;
static int[] e = new int[N];
static int[] ne = new int[N];
static int head;
static int idx;
static void init(){
head = 0;
ne[head] = -1;
idx = 1;
}
//x插入到头结点
static void add_to_head(int x){
ne[idx]=head;
head = idx;
e[idx] = x;
idx++;
}
//将x插到下标为k的点后面
static void add(int k, int x){
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
//将下标是k的后面的结点删除
void remove(int k){
ne[k] = ne[ne[k]];
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
init();
while(M!=0){
String m = sc.next();
if(m.equals("H")){
int x = sc.nextInt();
add_to_head(x);
}else if(m.equals("D")){
int k =sc.nextInt();
if(k == 0) head = ne[head];
else{
remove(k);
}
}else if(m.equals("I")){
int k = sc.nextInt(),x = sc.nextInt();
add(k,x);
}
M--;
}
for (int i = head; ne[i] != -1; i = ne[i]){
System.out.print(e[i]+" ");
}
}
}