单链表 常用操作（golang）

（单链表备忘记录）
知识点：

1. 单链表结构
2. 创建链表方法
   1. 头插法创建
   2. 尾插法创建
3. 遍历链表
4. 逆序反转链表
   1. 迭代
   2. 递归
   3. 头插法
   4. 就地逆置
5. 判断链表中是否有环
6. 链表中环的入口点
7. 链表中环的长度
8. 链表总长度

---

---

1. 单链表结构

data. 数据
next. 指向下一个链表节点的指针

type Node struct {
    data int
    next *Node
}

2. 创建链表方法

简单的可以一行行敲着创建，先创建node1，然后node2,
然后链起来node1.next=&node2
1. 头插法创建

/*头插法 创建链表*/
func CreateNodeInsterOnHead(listData []int) *Node {
    if len(listData) == 0 {
        return &Node{data: 0}
    }
    head := &Node{data: listData[0]}
    for _, v := range listData[1:] {
        node := &Node{data: v}
        node.next = head //新节点的next指向头head
        head = node//头head换成新节点
    }
    return head
}

传入 「1 2 3 4 5 6 7 8 9 10」
输出 「10 9 8 7 6 5 4 3 2 1」
2. 尾插法创建

/*尾插法创建链表*/
func CreateNodeInsterOnTail(listData []int) *Node {
    if len(listData) == 0 {
        return &Node{data: 0}
    }
    head := &Node{data: listData[0]}
    end := head //end 记录链表的尾，不断向end后插入新节点
    for _, v := range listData[1:] {
        end.next = &Node{data: v}
        end = end.next //移动end指针，指向新的尾节点
    }
    return head
}

传入 「1 2 3 4 5 6 7 8 9 10」
输出 「1 2 3 4 5 6 7 8 9 10」

3. 遍历链表

func printNode(node *Node) {
    if node == nil || node.next == nil {
        return
    }
    cur := node
    for cur != nil {
        fmt.Printf("%d ", cur.data)
        cur = cur.next
    }
}

4. 逆序反转链表

4.1 迭代

func ReverseNode1(head *Node) *Node {
    if head == nil || head.next == nil {
        return head
    }
    var prev *Node = nil
    var cur *Node = head
    var end *Node = head.next
    for {
        cur.next = prev //当前结点指向前一个节点
        if end == nil {
            break
        }
        prev = cur     //指针后移
        cur = end      //指针后移，处理下一个节点
        end = end.next //temp作为中间节点，记录当前结点的下一个节点的位置
    }
    head = cur
    return head
}

4.2 递归

func ReverseNode2(head *Node) *Node {
    if head == nil || head.next == nil {//递归的出口
        return head
    } else {
        //一直递归，找到链表中最后一个节点
        new_head := ReverseNode2(head.next)

        //当逐层退出时，new_head 的指向都不变，一直指向原链表中最后一个节点；
        //递归每退出一层，函数中 head 指针的指向都会发生改变，都指向上一个节点。

        //每退出一层，都需要改变 head->next 节点指针域的指向，同时令 head 所指节点的指针域为 NULL。
        head.next.next = head
        head.next = nil
        //每一层递归结束，都要将新的头指针返回给上一层。由此，即可保证整个递归过程中，能够一直找得到新链表的表头。
        return new_head
    }
}

4.3 头插法

func ReverseNode3(head *Node) *Node {
    var new_head *Node = nil
    var temp *Node = nil
    if head == nil || head.next == nil {
        return head
    }
    for head != nil {
        temp = head
        //将 temp 从 head 中摘除
        head = head.next
        //将 temp 插入到 new_head 的头部
        temp.next = new_head
        new_head = temp
    }
    return new_head
}

4.4 就地逆置

func ReverseNode4(head *Node) *Node {
    var beg *Node = nil
    var end *Node = nil
    if head == nil || head.next == nil {
        return head
    }
    beg = head
    end = head.next
    for end != nil {
        //将 end 从链表中摘除
        beg.next = end.next
        //将 end 移动至链表头
        end.next = head
        head = end
        //调整 end 的指向，另其指向 beg 后的一个节点，为反转下一个节点做准备
        end = beg.next
    }
    return head
}

5. 判断链表中是否有环

快慢指针

/*
* 链表是否有环
* is 是否
* meet 有环是返回快慢指针的相遇节点
*/
func isRingLinkNode(head *Node) (is bool, meet *Node) {
    slow := head
    fast := head
    for fast != nil && fast.next != nil {
        slow = slow.next
        fast = fast.next.next
        if slow == fast {
            return true, slow
        }
    }
    return false, nil
}

6. 链表中环的入口点

func findRingeEntry(head *Node) *Node {
    slow := head
    fast := head
    for fast != nil && fast.next != nil {
        slow = slow.next
        fast = fast.next.next
        if slow == fast {
            break
        }
    }

    if fast == nil || fast.next == nil {
        return nil
    }
    slow = head //慢指针重新指向头节点
    for slow != fast {
        slow = slow.next
        fast = fast.next
    }
    return slow
}

相遇后，slow继续一次移动一个节点，新另一node从链表头开始一次移动一个节点。

7. 链表中环的长度

//计算单链表环的长度
func ringLength(head *Node) int {
    //首先通过上面的方法判断，链表是否有环，并返回快慢指针的相遇点
    is, meet := isRingLinkNode(head)
    if is == false {
        return 0 //没有环，则直接返回
    }
    tmp := meet //tmp 停留在相遇点不再移动
    meet = meet.next
    len := 1
    for tmp != meet {
        len++
        meet = meet.next
    }
    return len
}

先用快慢指针相遇，相遇后记录相遇点，然后继续next向下走并记录走了几步，
再次相遇时即环长度。

8. 链表总长度

总长度 = 头到入口点长度 + 环到长度