时间限制：1.000S 空间限制：32MB
题目描述
本题考察链表的基本操作。温馨提示：本题较为复杂，需要细心多花一些时间。
输入描述
输入数据只有一组，第一行有n+1个整数，第一个整数是这行余下的整数数目n，后面是n个整数。
这一行整数是用来初始化列表的，并且输入的顺序与列表中的顺序相反，也就是说如果列表中是1、2、3那么输入的顺序是3、2、1。
第二行有一个整数m，代表下面还有m行。每行有一个字符串，字符串是“get”，“insert”，“delete”，“show”中的一种。
如果是“get”，代表获得第a个元素。（a从1开始计数）
如果是“delete”，代表删除第a个元素。（a从1开始计数）
如果是“insert”，则其后跟着两个整数a和e，代表在第a个位置前面插入e。（a从1开始计数）
“show”之后没有正数，直接打印链表全部内容。
输出描述
如果获取成功，则输出该元素；
如果删除成功，则输出“delete OK”；
如果获取失败，则输出“get fail”
如果删除失败，则输出“delete fail”
如果插入成功，则输出“insert OK”，否则输出“insert fail”。
如果是“show”，则输出列表中的所有元素，如果列表是空的，则输出“Link list is empty”
注：所有的双引号均不输出。
输入示例
3 3 2 1
21
show
delete 1
show
delete 2
show
delete 1
show
delete 2
insert 2 5
show
insert 1 5
show
insert 1 7
show
insert 2 5
show
insert 3 6
show
insert 1 8
show
get 2
输出示例
1 2 3
delete OK
2 3
delete OK
2
delete OK
Link list is empty
delete fail
insert fail
Link list is empty
insert OK
5
insert OK
7 5
insert OK
7 5 5
insert OK
7 5 6 5
insert OK
8 7 5 6 5
7
提示信息
初始化链表的元素是倒序的，这个使用题目中创建列表的方法（从头部插入）就可以了。
答案
package main
import (
"bufio"
"os"
"fmt"
"strings"
"strconv"
)
var (
n int
arr []string
linkedList *LinkedList
idx int
val string
success bool
list []string
)
func main() {
input := bufio.NewScanner(os.Stdin)
for input.Scan() {
arr = strings.Fields(input.Text())
n, _ = strconv.Atoi(arr[0])
arr = arr[1:n + 1]
linkedList = NewLinkedList()
for _, val = range arr {
linkedList.Insert(1, val)
}
input.Scan()
n, _ = strconv.Atoi(input.Text())
for ; n > 0; n-- {
input.Scan()
arr = strings.Fields(input.Text())
switch arr[0] {
case "get":
idx, _ = strconv.Atoi(arr[1])
val, success = linkedList.Get(idx)
if !success {
fmt.Println("get fail")
} else {
fmt.Println(val)
}
case "insert":
idx, _ = strconv.Atoi(arr[1])
success = linkedList.Insert(idx, arr[2])
if !success {
fmt.Println("insert fail")
} else {
fmt.Println("insert OK")
}
case "delete":
idx, _ = strconv.Atoi(arr[1])
success = linkedList.Delete(idx)
if !success {
fmt.Println("delete fail")
} else {
fmt.Println("delete OK")
}
case "show":
list = linkedList.List()
if len(list) == 0 {
fmt.Println("Link list is empty")
} else {
fmt.Println(strings.Join(list, " "))
}
}
}
}
}
type LinkedList struct {
dummy *LinkedListNode
Size int
}
type LinkedListNode struct {
Val string
Next *LinkedListNode
}
func NewLinkedList() *LinkedList {
return &LinkedList{
dummy: &LinkedListNode{},
}
}
func (l *LinkedList) Get(idx int) (string, bool) {
if l.Size < idx {
return "", false
}
cur := l.dummy
for ; idx > 0; idx-- {
cur = cur.Next
}
return cur.Val, true
}
func (l *LinkedList) Insert(idx int, val string) bool {
if l.Size + 1 < idx {
return false
}
prev := l.dummy
idx--
for ; idx > 0; idx-- {
prev = prev.Next
}
node := &LinkedListNode{
Val: val,
Next: prev.Next,
}
prev.Next = node
l.Size++
return true
}
func (l *LinkedList) Delete(idx int) bool {
if l.Size < idx {
return false
}
prev := l.dummy
idx--
for ; idx > 0; idx-- {
prev = prev.Next
}
prev.Next = prev.Next.Next
l.Size--
return true
}
func (l *LinkedList) List() []string {
res := make([]string, 0, l.Size)
cur := l.dummy
for i := 0; i < l.Size; i++ {
cur = cur.Next
res = append(res, cur.Val)
}
return res
}