Golang如何实现单链表找环

这篇文章将为大家详细讲解有关Golang如何实现单链表找环，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。

问题：一个单向链表，怎样怎么检测是否有环，环的初始节点是什么？

package main

import (
    "fmt"
)

type ListNode struct {
    value int
    next  *ListNode
}

func NewListNode(i int) *ListNode {
    val := new(ListNode)
    val.value = i
    return val
}

func main() {
    a1 := NewListNode(1)
    a2 := NewListNode(2)
    a3 := NewListNode(3)
    a4 := NewListNode(4)
    a5 := NewListNode(5)

    // 1→2→3→4→5
    //     ↑⎽⎽⎽⌟   

    a1.next = a2
    a2.next = a3
    a3.next = a4
    a4.next = a5
    a5.next = a3
    head := DetectCycle(a1)
    fmt.Println(head.value)
}

func DetectCycle(head *ListNode) *ListNode {
    fast := head
    slow := head
    for {
        if fast.next == nil || slow.next == nil {
            break
        }
        fast = fast.next.next
        slow = slow.next
        if fast == slow {
            // 找到快慢指针相遇点
            break
        }
    }
    if fast == nil || slow == nil {
        return nil
    }
    // 找到快慢指针相遇点后，快慢指针一样的速度移动，找到环的起点
    slow = head
    for {
        if fast == slow {
            break
        }
        fast = fast.next
        slow = slow.next
    }
    return slow
}

关于“Golang如何实现单链表找环”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。