leetcode707设计链表

链表设计，包括，头插，尾插，删除， 查询

链表toString()

func (this *MyLinkedList) ToString()string{
    node := this.Head
    str := ""
    for node!=nil{
        str += fmt.Sprintf("%v-->", node.Val)
        node = node.Next
    }
    str += fmt.Sprintf("nil")
    fmt.Println(str)
    return str
}

package main

import "fmt"

// 链表节点
type listNode struct{
    Val int
    Next *listNode
}

// MyLinkedList 存链表数据结构
type MyLinkedList struct{
    Head *listNode
    Lens int
}

// Constructor 初始化链表， 返回链表节点
func Constructor()MyLinkedList{
    return MyLinkedList{
        Head: nil,
        Lens: 0,
    }
}

func (this *MyLinkedList)Get(index int)int{
    // 如果索引<0, 或者索引大于链表长度-1
    if index<0||index>this.Lens-1{
        return -1
    }
    //如果链表长度=0， 返回头结点
    if index==0{
        return this.Head.Val
    }
    node := this.Head
    // 如果节点的下一个！=nil
    for node.Next!=nil{
        index--
        // 注意下面两行的顺序，不要颠倒，要取node.的下一个节点
        node = node.Next
        if index==0{
            // 说明找到了
            return node.Val
        }
    }
    return -1
}
// AddAtTail 尾插
func (this *MyLinkedList) AddAtTail(val int) {
    // 如果长度=0，在尾部增加，就是在头部增加，不等于0，就正常增加
    if this.Lens == 0{
        this.AddAtHead(val)
    }else{
        node := this.Head
        // 一直循环到链表尾
        for node.Next!=nil{
            node = node.Next
        }
        // 要增加的节点
        tail := &listNode{
            Val:  val,
            Next: nil,
        }
        // 链表尾节点等于新定义的尾节点
        node.Next = tail
        // 长度增加
        this.Lens++
    }
}

// AddAtIndex 在指定索引位置添加
func (this *MyLinkedList) AddAtIndex(index int, val int){
    // 如果长度等于索引，则在尾部添加（题目要求）
    if this.Lens==index{
        this.AddAtTail(val)
        return
    }
    // 长度小于索引，返回
    if this.Lens-1<index{
        return
    }
    //索引小于等于0， 头插。（题目要求）
    if index<=0{
        this.AddAtHead(val)
        return
    }
    // 正常流程
    node := this.Head
    // 节点要停在要插入的节点的前一个，这样单链表才能正常在他的后面插入
    for index>1{
        index--
        node = node.Next
    }
    // 先把新节点指向要插入的节点， 然后再把要插入姐点的前一个节点指向新的节点
    node.Next = &listNode{Val: val, Next: node.Next}
    this.Lens++
}

// AddAtHead 在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
func (this *MyLinkedList) AddAtHead(val int){
    node := &listNode{
        Val:  val,
        Next: nil,
    }
    // 判断一下头结点时候是空的
    if this.Head == nil{
        // 空的话，他的头指向新节点，next指向nil
        this.Head = node
        this.Head.Next = nil
        this.Lens++
    }else{
        // 不为空的话，头插，先备份头结点
        bak := this.Head
        // 头结点等于新节点，然后头结点的下一个节点指向原头节点
        this.Head = node
        this.Head.Next = bak
        // 长度增加一
        this.Lens++
    }
}

// DeleteAtIndex 删除指定索引位置元素
func (this *MyLinkedList) DeleteAtIndex(index int){
    // 如果索引小于0，或者长度小于索引
    if index<0||index>this.Lens-1{
        return
    }else{
        // 如果长度等于0，然后要判断长度，小于2和大于2
        if index==0{
            // 小于2,头结点置空
            if this.Lens<2{
                this.Head = nil
                this.Lens--
                return
            }else{
                // 头节点等于头结点的下一个
                this.Head = this.Head.Next
                this.Lens--
                return
            }
        }
        // 其他就是正常情况，
        node := this.Head
        // 他也是要停在他的上一个节点，，然后node.Next = node.Next.Next
        for node.Next!=nil&&index>1{
            index--
            node = node.Next
        }
        node.Next = node.Next.Next
        this.Lens--
    }
}
// 格式化输出
func (this *MyLinkedList) ToString()string{
    node := this.Head
    str := ""
    for node!=nil{
        str += fmt.Sprintf("%v-->", node.Val)
        node = node.Next
    }
    str += fmt.Sprintf("nil")
    fmt.Println(str)
    return str
}
func main() {
    l := Constructor()
    //l.AddAtHead(0)
    //l.ToString()
    //l.AddAtHead(1)
    //l.ToString()
    //l.AddAtHead(2)
    //l.ToString()
    //l.AddAtTail(4)
    //l.AddAtTail(5)
    //l.AddAtTail(6)
    //l.ToString()
    //l.AddAtIndex(6, 66)
    //l.ToString()
    //l.DeleteAtIndex(2)
    //l.ToString()
    //l.DeleteAtIndex(0)
    //l.ToString()
    //l.AddAtHead(1)
    //l.ToString()
    //l.DeleteAtIndex(0)
    //l.ToString()
    l.AddAtHead(1)
    l.AddAtTail(3)
    //l.ToString()
    l.AddAtIndex(1,2)
    l.ToString()
    fmt.Println("1:",l.Get(1))
    l.DeleteAtIndex(1)
    fmt.Println("2:", l.Get(1))
    fmt.Println("3:",l.Get(3))
    l.ToString()
    l.DeleteAtIndex(3)
    l.ToString()

    l.DeleteAtIndex(0)
    fmt.Println(l.Get(0))
    l.DeleteAtIndex(0)
    fmt.Println(l.Get(0))
    l.ToString()
}