单链

链表

链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据

package main
import (
    "errors"
    "fmt"
)
type Node struct {
    Value int
    Next *Node
}
//头节点
type List struct{
    Head *Node
}
//是否为空
func (this *List) IsEmpty() bool {
    if this.Head == nil{
        return true
    }
    return false
}
//是否最后一个节点
func (this *List) IsLast() bool {
    if this.Head.Next == nil{
        return true
    }
    return false
}
// 长度
func (this *List) Len() int{
    if this.IsEmpty(){
        return 0
    }
    length := 1
    current := this.Head
    for  current.Next != nil {
        length ++
        current = current.Next
    }
    return length
}
//首部插入
func (this *List) Add(v int) {
    Head := &Node{Value:v}
    Head.Next = this.Head //将新创建的Head的next指向当前Head
    this.Head = Head  // 将当前Head更新为新创建的Head
}
//尾部插入
func (this *List) Append(v int) {
    Head := &Node{Value:v}
    if this.IsEmpty(){
        // 如果当前链表为空，直接插入首部
        this.Add(v)
    }else {
        last := this.Head
        // 遍历到最后一个节点
        for last.Next != nil{
            last = last.Next
        }
        last.Next = Head
    }
}
// 插入
func (this *List) Insert(index,v int) {
    if index<=0{
        this.Add(v)
    }else if index >= this.Len(){
        this.Append(v)
    }else {
        previous := this.Head
        for i:=0;i<index-1;i++{
            previous = previous.Next
        }
        current := previous.Next //index节处现有的Head点
        Head := &Node{Value:v}
        Head.Next = current   //插入的节点的next指向index处现有的Head节点
        previous.Next = Head  // index处现有Head节点的上一个Head的next指向插入的Head
    }
}
// 删除
func (this *List) DelByIndex(index int) error{
    current := this.Head
    if index <= 0 {  //判断删除的是否是首节点
        this.Head = current.Next
    }else if index>= this.Len(){
        return errors.New("index out of range")
    }else {
        for i:=0;i<index-1;i++{
            current = current.Next
        }
        //将需要被删除的节点的上一个节点的next指向->被删除节点的next指向的Head
        current.Next = current.Next.Next
    }
    return nil
}
// 删除
func (this *List) DelByValue(value int){
    current := this.Head
    if value == current.Value{ //判断删除的是否是首节点
        this.Head = current.Next
    }else {
        for current.Next != nil {
            if current.Next.Value == value{
                current.Next = current.Next.Next
            }else {
                current = current.Next
            }
        }
    }
}
// 查找
func (this *List) Find(index int) (int,error){
    current := this.Head
    if index <= 0 {
        return current.Value,nil
    }else if index >= this.Len(){
        return 0,errors.New("index out of range")
    }
    for i:=0;i<index;i++{
        current = current.Next
    }
    return current.Value,nil
}
// 遍历
func (this *List) ForEach(){
    current := this.Head
    for {
        fmt.Println(current.Value)
        if current.Next == nil{
            break
        }
        current = current.Next
    }
}
func main() {
    list := & List{}
    list.Append(1)
    list.Append(2)
    list.Append(3)
    list.ForEach()
    list.Add(0)
    list.ForEach()
    list.DelByIndex(3)
    list.ForEach()
    list.DelByValue(2)
    list.ForEach()
    v,_ := list.Find(1)
    fmt.Println("index=0;value=",v)
}

链表反转

这里引发一个关于指针的问题
两个指针类型互指，结果会如何？

func main() {
    var a *int              // a为nil
    var b = new (int)       // b为0xc00000a110
    var c = new (int)       // c为0xc00000a118
    a = b                     // 此时a为0xc00000a110
    *b = 2                  // 将地址0xc00000a110 指向值为2的一块内存
    b = c                   // 此时b为0xc00000a118，注意这里不会改变a
    *b = 1                  // 将地址0xc00000a118 指向值为1的一块内存
    fmt.Println(*a,*b,*c)   // 2 1 1
}

链表反转的思想：

可以看出来

• pre是cur的最前面那位（pre = cur）
• cur就是当前位的后面链表元素（cur = cur.Next）
• cur.Next肯定是接pre（cur.Next = pre）

  // 单链反转
  func (this *List) Reversr(){
    Head := this.node  // 头节点
    var pre *Node // 定一个空node
    var temp *Node //临时node
    for current != nil{
        temp = current.Next  //让临时node保存头得下一个节点
        current.Next = pre   //将头节点指向前一个节点
        pre = current        //更新前一个节点
        current = temp       //更新头节点
    }
    this.Head = pre
  }
  

判断链表有无环

对于这个问题我们可以采用“快慢指针”的方法。就是有两个指针fast和slow，开始的时候两个指针都指向链表头head，然后在每一步

操作中slow向前走一步即：slow = slow->next，而fast每一步向前两步即：fast = fast->next->next。

由于fast要比slow移动的快，如果有环，fast一定会先进入环，而slow后进入环。当两个指针都进入环之后，经过一定步的操作之后

二者一定能够在环上相遇，并且此时slow还没有绕环一圈，也就是说一定是在slow走完第一圈之前相遇。证明可以看下图：

func (this *List) HasLoop() bool {
    var (
        res        bool
        slow, fast = this.Head, this.Head
    )

    for slow != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next
        if slow == fast {
            res = true
            break
        }
    }

    return res
}

删除倒数第n个节点

快慢指针解法

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head} // 辅助头节点，它的好处是处理边界问题
    slow, fast := dummy, dummy

    // fast先走n步
    for n > 0 && fast != nil {
        fast = fast.Next
        n--
    }

    // 当fast走到最后一个有效节点，那么slow就走到了待删除节点的上一个节点
    for fast.Next != nil {
        fast = fast.Next
        slow = slow.Next
    }

    slow.Next = slow.Next.Next

    return dummy.Next
}

结构优化

做任何事情至少都会有两个步骤，实现与优化

type Node struct { 
    Value int
    Next *Node
}

type List struct{
    // 1.很显然这种结构体在并发中是不安全的，可以加读写锁
    // mutex *sync.RWMutex
    // 2.如果经常有判断长度的操作，可以加个size字段，将时间复杂度从O(n)变为O(1)
    // size uint
    Head *Node
}