707. 设计链表#

1
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
2

3
在链表类中实现这些功能：
4

5
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
6
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
7
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
8
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
9
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
10

11

12
MyLinkedList linkedList = new MyLinkedList();
13
linkedList.addAtHead(1);
14
linkedList.addAtTail(3);
15
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
16
linkedList.get(1);            //返回2
17
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
18
linkedList.get(1);            //返回3
19

20
所有val值都在 [1, 1000] 之内。
21
操作次数将在  [1, 1000] 之内。
22
请不要使用内置的 LinkedList 库。

1
type MyLinkedList struct {
2
 Val  int
3
 Next *MyLinkedList
4
}
5

6
func Constructor() MyLinkedList {
7
    // 该节点为头结点，不会用到
8
 return MyLinkedList{
9
        Val: -1,
10
        Next: nil,
11
    }
12
}
13

14
func (this *MyLinkedList) Get(index int) int {
15
 tmp := this.Next
16
 for i := 0; tmp != nil; i++ {
17
        if i == index {
18
            return tmp.Val
19
        } else {
20
            tmp = tmp.Next
21
        }
22
 }
23
    return -1
24
}
25

26
func (this *MyLinkedList) AddAtHead(val int) {
27
 this.Next = &MyLinkedList{
28
  Val:  val,
29
  Next: this.Next,
30
 }
31
}
32

33
func (this *MyLinkedList) AddAtTail(val int) {
34
 tmp := this
35
 for tmp.Next != nil {
36
  tmp = tmp.Next
37
 }
38
 tmp.Next = &MyLinkedList{
39
  Val:  val,
40
  Next: nil,
41
 }
42
}
43

44
func (this *MyLinkedList) AddAtIndex(index int, val int) {
45
 if index <= 0 {
46
  this.AddAtHead(val)
47
        return
48
 }
49
    tmp := this.Next
50
    // 遍历到index处
51
    for i := 1; i < index && tmp.Next != nil; i++ {
52
        tmp = tmp.Next
53
    }
54
    // index超出链表长度
55
    if tmp == nil {
56
        return
57
    }
58
    tmp.Next = &MyLinkedList{
59
        Val:  val,
60
        Next: tmp.Next,
61
    }
62
}
63

64
func (this *MyLinkedList) DeleteAtIndex(index int) {
65
    // 空链表
66
    if this.Next == nil {
67
        return
68
    }
69
 if index <= 0 {
70
  this.Next = this.Next.Next
71
  return
72
 }
73
 tmp := this.Next
74
 for i := 1; i < index && tmp.Next != nil; i++ {
75
  tmp = tmp.Next
76
 }
77
    // index超出链表长度
78
 if tmp.Next == nil {
79
  return
80
 }
81
 tmp.Next = tmp.Next.Next
82
}
83

84

85
/**
86
 * Your MyLinkedList object will be instantiated and called as such:
87
 * obj := Constructor();
88
 * param_1 := obj.Get(index);
89
 * obj.AddAtHead(val);
90
 * obj.AddAtTail(val);
91
 * obj.AddAtIndex(index,val);
92
 * obj.DeleteAtIndex(index);
93
 */