Golang如何实现单链表找环

107次阅读
没有评论

共计 973 个字符,预计需要花费 3 分钟才能阅读完成。

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

问题:一个单向链表,怎样怎么检测是否有环,环的初始节点是什么?

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

正文完
 
丸趣
版权声明:本站原创文章,由 丸趣 2023-08-16发表,共计973字。
转载说明:除特殊说明外本站除技术相关以外文章皆由网络搜集发布,转载请注明出处。
评论(没有评论)