题目描述

实现一个单链表，链表初始为空，支持三种操作：

(1) 向链表头插入一个数；

(2) 删除第k个插入的数后面的数；

(3) 在第k个插入的数后插入一个数

现在要对该链表进行M次操作，进行完所有操作后，从头到尾输出整个链表。

注意：

题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数，则按照插入的时间顺序，这n个数依次为：第1个插入的数，第2个插入的数，…第n个插入的数。

输入格式

第一行包含整数M，表示操作次数。

接下来M行，每行包含一个操作命令，操作命令可能为以下几种：

(1) “H x”，表示向链表头插入一个数x。

(2) “D k”，表示删除第k个输入的数后面的数（当k为0时，表示删除头结点）。

(3) “I k x”，表示在第k个输入的数后面插入一个数x（此操作中k均大于0）。

输出格式

共一行，将整个链表从头到尾输出。

数据范围

1≤M≤100000
所有操作保证合法。

输入样例：

10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6

输出样例：

6 4 6 5

单链表具体分析

本题用的是数组模拟链表，数组模拟链表也叫做静态链表，它的优点是速度快，缺点是会浪费内存

单链表

e[i]：当前节点
en[i]：表示节点i的next指针
idx：存储当前已经用到了哪个点

1.插入元素到表头

//插入到头指针
private static void addToHead(int v){
    e[idx]=v;//赋值
    ne[idx]=head;//当前指针在next指向head
    head=idx;//
    idx++;
}

2.插入元素普通节点

//将v插到下标是k的点后面
private static void add(int k,int v){
    e[idx]=v;
    ne[idx]=ne[k];
    ne[k]=idx;
    idx++;
}

3.删除节点

// 将下标是k的点后面的点删掉
private static void remove(int k){
    ne[k]=ne[ne[k]];
}

完整代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    private static int N=100010;
    private static int head;//头节点
    private static int[] e=new int[N];//节点i的值
    private static int[] ne=new int[N];//节点i的nex指针
    private static int idx;//当前使用到数组的下一个下标

    public static void main(String[] args)  throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(bufferedReader.readLine());

        init();

        while (m-->0){
            String[] s=bufferedReader.readLine().split(" ");

            if(s[0].equals("H")){//插入头节点
                int v=Integer.parseInt(s[1]);
                addToHead(v);
            }else if(s[0].equals("I")){//插入
                int k=Integer.parseInt(s[1]);
                int v=Integer.parseInt(s[2]);
                add(k-1,v);
            }else if(s[0].equals("D")){//删除
                int k=Integer.parseInt(s[1]);
                if(k==0){//题：k=0,删除头节点
                    head=ne[head];
                }else {
                    remove(k-1);
                }
            }

        }

        for(int i=head;i!=-1;i=ne[i]){
            System.out.print(e[i]+" ");
        }

    }

    //初始化
    private static void init(){
        head=-1;
        idx=0;
    }

    //插入到头指针
    private static void addToHead(int v){
        e[idx]=v;//赋值
        ne[idx]=head;//当前指针在next指向head
        head=idx;//
        idx++;
    }

    //将v插到下标是k的点后面
    private static void add(int k,int v){
        e[idx]=v;
        ne[idx]=ne[k];
        ne[k]=idx;
        idx++;
    }

    // 将下标是k的点后面的点删掉
    private static void remove(int k){
        ne[k]=ne[ne[k]];
    }

}