简介

有环链表，也就是一个链表中至少有一个环。

双向链的每个节点的prev指向上一个节点，next指针指向下一个节点。

1 一个链表，判断链表中是否有环。

思路: 快慢指针，设定两个指针，fast 步长为2，slow 步长为1，遍历，
从同一点出发，如果两个指针相遇，那么表示这个链表有环。
如果没有环，那么fast 先达到 NULL

快慢指针相遇时的循环次数等于环的长度。

如何找出 环链表的入口

    思路: 快慢指针相遇点 到环入口的距离 = 链表起始点到环 入口的距离

如何求解环的长度

    思路:当两个指针相遇Z时，此时slow走过的路径为 a + b， fast走过的路径为 a+b+c+b, 因为fast步长为 slow的两边，所以 2（a+b）=a+b+c+b

所以 a = c， 环的长度为 b + c，也就是 a+b，即slow走过的步长如何判断两个链表是否相交

    思路: 如果两个链表相交，那么这两个链表尾节点 一定相同，直接判断尾节点是否相同即可，

2 例子:环形链表可以拆分为两个Y链表。

环形链表用例: pos 表示 链表尾部节点 执行该链表的 哪一个节点：

        输入:
        [3,2,0,-4]    pos = 1  # 表示1个环 -4 与 2相 链
            |____|

        输出:
        tail connects to node index 1

        输入:
            [1, 3, 4]  pos =0   #  表示 4 与 1 首尾相连
            |_____|
        输出:
            tail connects to node index 0

        输入:
            [1, 2]  pos = 0  # 表示 2 与 1 连
            |__|
        输出:
            tail connects to node index 0

        输入:
            [-1]
            -1  # 表示没有 环
        输出:
            null

3 实现

我们使用双向链表实现环形链接。首先定义链表的每个节点

   type Node struct {
        Number int
        Prev   *Node
        Next   *Node
}

  type Doublist struct {
        Lens int
        Head *Node
        Tail *Node
}

func MakeDlist() *Doublist {
        return &Doublist{}
}

实现对节点的有序放入

func (th *Doublist) Pushback(n *Node) bool {
        if n == nil {
                return false
        }
        currentNode := th.Head
        if currentNode == nil {

                return th.NewNodeList(n)
        } else {
                inDex, insertNode := th.Lesseq(n)
                if inDex == 0 {
                        return th.PushHead(n)
                } else if inDex == (th.Lens-1) && insertNode == nil {
                        return th.Append(n)
                } 

                n.Next = insertNode
                n.Prev = insertNode.Prev
                if insertNode.Prev != nil {
                        insertNode.Prev.Next = n
                }

                insertNode.Prev = n
                th.Lens += 1
                return true
        }
}

显示链表的值

func (th *Doublist) Display() {

        node := th.Head
        t := 0
        Logg.Println(node.Number)
        for node != nil {
                t += 1
                if t >= th.Lens {
                        break
                }

                node = node.Next
                Logg.Println(node.Number)
        }

        Logg.Println("length:", th.Lens)
}

然后定义环形链表

   type CycleLinked struct {
        Size  int
        Items *Doublist
}

链表缓存通道

type MyChan struct {
        Read  <-chan *Node
        Input chan<- *Node
}

添加多个节点到链表

func (cl *CycleLinked) SetItems(n int) *CycleLinked {
        if n <= cl.Size {
                cl.Items = MakeDlist()
                for i := 0; i < n; i++ {
                        cl.Items.Pushback(&Node{Number: i})
                }
        }

        return cl

}

使用有环链表，创建 空链表，填入数字

        tLinked := MakeEmptyLinked(8)

        numberC := tLinked.SetItems(tLinked.Size)

        cNode := numberC.Items.Head
        for cNode != nil {
                Logg.Printf("%+v\n", cNode)
                cNode = cNode.Next
        }
}

3 小结

该文本为工具使用解说。使用双指针法来判断一个单向链表是否存在环，而最后判断环的位置时，则需要利用快慢指针相遇后的特性来定义第三个指针，从而找到入口位置，其实找到环的位置代码不难，关键是推理的过程需要去理解。

源码地址:

 https://github.com/hahamx/utools/blob/main/utils/circled/main.go