导读另一种链表算法。 检测链表中的循环。 这实际上并没有那么糟糕。至少有 3 种不同的方法可以实现 o(n) 时间。 最简单的方法需要修改链表节点以包含一个表示节点是否已被访问的标志
另外一种链表算法。
检测链表中的循环。
事实上，这并没有那么糟糕。至少有 3 各种各样的方法都能实现。 o(n) 时间。
最简单的方法是修改链表节点，包括一个标志，表示节点是否已经被访问。在遍历列表的过程中，如果遇到已经访问过的节点，就会有一个循环。
另一种技术使用哈希图，包括访问节点或引用它们。当列表被遍历时，节点或其引用被插入到分散列中。如果我们遇到一个已经在哈希图中表达的节点，就会有一个循环。虽然这项技术只需要一次遍历，但它确实需要更多的内存，因为哈希图。
我将在本文中使用它。 floyd 检测循环的算法。很简单。
funcDetectCycle[Tany](llLinkedList[T])bool{
slow:=ll.Head
fast:=ll.Head
forfast!=nil&&fast.Next!=nil{
slow=slow.Next
fast=fast.Next.Next
iffast==slow{
returntrue
}
}
returnfalse
}
此技术使用 2 指向列表的指针。当遍历列表时，一个指针一次移动一个节点，另一个指针一次移动两个节点。如果两个指针相遇，就会有一个循环。
为何这样有效？两个指针之间的距离随着列表的遍历而增加。假如有循环，快指针就会“绕”慢指针。
是否有更高效的实现方法？是否缺乏任何边界条件？请在评论中告诉我。
谢谢！
本文及本系列所有文章的代码可在此找到。
上述是检测链表中循环的详细内容，更多请关注其他相关文章！
免责声明：本文来源于网络，如有侵权请联系我们！