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

(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

Go 代码

package main

import "fmt"

// head 表示头结点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx 存储当前已经用到了哪个点
var (
    head int
    e  = make([]int,100010)
    ne = make([]int,100010)
    idx int
)

// 初始化
func new() {
    head = -1
    idx = 0
}

// 将 x 插入头节点
func addToHead(x int) {
    e[idx] = x
    ne[idx] = head
    head = idx
    idx++
}

// 将 x 插入下标是 k 的节点后面
func add(k, x int) {
    e[idx] = x
    ne[idx] = ne[k]
    ne[k]= idx
    idx++
}

// 将下标是 k 的节点后面的点删掉
func remove(k int) {
    ne[k] = ne[ne[k]]
}

// 遍历链表
func traverse(head int) []int {
    res := []int{}
    for i := head; i != -1; i = ne[i] {
        res = append(res, e[i])
    }
    return res
}

func main() {
    var m int
    fmt.Scanf("%d", &m) // 第一行包含整数M，表示操作次数。
    new()
    for ; m > 0; m-- { // 接下来M行，每行包含一个操作命令
        var op string
        fmt.Scanf("%s", &op)
        switch op {
        case "H":
            var x int
            fmt.Scanf("%d", &x)
            addToHead(x)
        case "I":
            var k, x int
            fmt.Scanf("%d%d",&k,&x)
            add(k-1, x)
        case "D":
            var k int
            fmt.Scanf("%d", &k)
            if k==0 {
                head = ne[head]
            } else {
                remove(k-1)
            }
        }
    }
    res := traverse(head)
    for i := range res {
        fmt.Printf("%d ", res[i])
    }
}

package main

import "fmt"

type link struct {
    head int   // 头节点下标
    e    []int // 数组 e 表示节点 i 的值
    ne   []int // 表示节点 i 的 next 指针
    idx  int   // 存储当前已经用到哪个点，相当于指针
}

func main() {
    var m int
    fmt.Scan(&m) // 第一行包含整数M，表示操作次数。
    l := new()
    for i := 0; i < m; i++ { // 接下来M行，每行包含一个操作命令
        var op string
        fmt.Scan(&op)
        switch op {
        case "H":
            var x int
            fmt.Scanf("%d", &x)
            l.addToHead(x)
        case "I":
            var k, x int
            fmt.Scanf("%d%d", &k, &x)
            l.add(k-1, x)
        case "D":
            var k int
            fmt.Scanf("%d", &k)
            if k == 0 {
                l.head = l.ne[l.head]
            } else {
                l.remove(k - 1)
            }
        }
    }
    res := l.traverse(l.head)
    for i := range res {
        fmt.Printf("%d ", res[i])
    }
}

// 初始化
func new() *link {
    return &link{
        head: -1,
        idx:  0,
        e:    make([]int, 100010),
        ne:   make([]int, 100010),
    }
}

// 将 x 插入头节点
func (l *link) addToHead(x int) {
    l.e[l.idx] = x
    l.ne[l.idx] = l.head
    l.head = l.idx
    l.idx++
}

// 将 x 插入下标是 k 的节点后面
func (l *link) add(k, x int) {
    l.e[l.idx] = x
    l.ne[l.idx] = l.ne[k]
    l.ne[k] = l.idx
    l.idx++
}

// 将下标是 k 的节点后面的点删掉
func (l *link) remove(k int) {
    l.ne[k] = l.ne[l.ne[k]]
}

// 遍历链表
func (l *link) traverse(head int) []int {
    var res []int
    for i := head; i != -1; i = l.ne[i] {
        res = append(res, l.e[i])
    }
    return res
}