设计链表

707. 设计链表

leetcode 链接

思路：

1.确定节点结构，包括当前 Val,以及下一个节点的指针 Next.

2.确定链表结构，包括链表的头节点 Head，以及链表的长度 Length。

3.确定链表的方法，包括获取链表中的某个节点的值 Get，向链表头部添加节点 AddAtHead，向链表尾部添加节点 AddAtTail，向链表中的某个位置添加节点 AddAtIndex，删除链表中的某个位置的节点 DeleteAtIndex。

4.实现 AddAtaTail, 和 AddAtIndex, DeleteAtIndex 方法时需要使用 dummy 节点，dummy 节点的 Next 指向链表的头节点 Head，这样可以避免在 AddAtaTail, 和 AddAtIndex, DeleteAtIndex 方法中对头节点 Head 的判断。

typescript 解法

// 暂无

go 解法

type Node struct {
    Val int
    Next *Node
}

type MyLinkedList struct {
    Arr *Node
    Length int
}


func Constructor() MyLinkedList {
    var arr *Node
    return MyLinkedList{
        Arr: arr,
        Length: 0,
    }
}


func (this *MyLinkedList) Get(index int) int {
    if index >= this.Length {
        return -1
    }
    current := this.Arr
    for index > 0 {
        current = current.Next
        index --
    }
    return current.Val
}


func (this *MyLinkedList) AddAtHead(val int)  {
    node := &Node{
        Val: val,
        Next: this.Arr,
    }
    this.Arr = node
    this.Length ++
}


func (this *MyLinkedList) AddAtTail(val int)  {
    node := &Node{
        Val: val,
    }
    dummy := &Node{
        Next: this.Arr,
    }
    current := dummy
    for current != nil && current.Next != nil {
        current = current.Next
    }
    current.Next = node
    this.Arr = dummy.Next
    this.Length ++
}


func (this *MyLinkedList) AddAtIndex(index int, val int)  {
    if index > this.Length {
        return
    }
    if index == 0 {
        this.AddAtHead(val)
        return
    }
    if index == this.Length {
        this.AddAtTail(val)
        return
    }
    node := &Node{
        Val: val,
    }
    dummy := &Node{
        Next: this.Arr,
    }
    current := dummy
    for index > 0 {
        current = current.Next
        index --
    }
    node.Next = current.Next
    current.Next = node
    this.Arr = dummy.Next
    this.Length ++
}


func (this *MyLinkedList) DeleteAtIndex(index int)  {
    if index >= this.Length || index < 0 {
        return
    }
    dummy := &Node{
        Next: this.Arr,
    }
    current := dummy
    for index > 0 {
        current = current.Next
        index --
    }
    current.Next = current.Next.Next
    this.Arr = dummy.Next
    this.Length --
}


/**
 * Your MyLinkedList object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Get(index);
 * obj.AddAtHead(val);
 * obj.AddAtTail(val);
 * obj.AddAtIndex(index,val);
 * obj.DeleteAtIndex(index);
 */