本文共 2061 字，大约阅读时间需要 6 分钟。

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

(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≤1000001≤M≤100000

输入样例：

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

输出样例：

6 4 6 5

思想：

在算法笔试中，我们不会去构建节点结构，而是直接用数组来模拟化链表，因为创建节点会非常耗时，会导致创建节点的过程中超时。

import java.io.*;import java.lang.Integer;class Main{        //N 限定范围    //e[N] 存储插入值    //ne[N] 存储当前节点的下一个节点的指针    //head 存储头结点    //idx 当前节点下标    static int N = 100010;    static int[] e = new int[N], ne= new int[N];    static int head, idx;    //初始化    static void init(){        head = -1; idx = 0;    }    //插入到头结点，保证最后的坐标是-1    static void addToHead(int x){        e[idx] = x; ne[idx] = head; head = idx++;    }    //插入到k后    static void add(int k, int x){        e[idx] = x; ne[idx] = ne[k]; ne[k] = idx++;    }    //删除k后    static void remove(int k){        ne[k] = ne[ne[k]];    }        public static void main(String[] args)throws Exception{        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));        int n = Integer.valueOf(buf.readLine());        init();        for(int i = 0; i < n; ++i){            String[] params = buf.readLine().split(" ");            if("H".equals(params[0])){                int x = Integer.valueOf(params[1]);                addToHead(x);            }else if("I".equals(params[0])){                int k = Integer.valueOf(params[1]);                int x = Integer.valueOf(params[2]);                add(k - 1, x);            }else{                int k = Integer.valueOf(params[1]);                if(k == 0){                    head = ne[head];                    continue;                }                remove(k - 1);            }        }        for(int i = head; i != -1; i = ne[i]){            System.out.printf("%d ", e[i]);        }    }}