弗洛伊德环路检测算法，用于检测线性数据结构中的环路

弗洛伊德环路是环路检测算法之一，用于检测给定的单向链表中的环路。

在弗洛伊德环路算法中，我们具有两个指针，最初指向头节点。在兔子和乌龟的故事中，兔子移动速度是乌龟的两倍，每当兔子到达路径末尾时，乌龟就会到达路径中间。

算法

  • 将兔子和乌龟初始化为链表的头节点。

  • 最初，兔子的移动速度是乌龟的两倍。

  • 将兔子和乌龟都向前移动，如果兔子到达链表的末尾，则返回，因为链表中没有循环。

  • 否则，兔子和乌龟都会向前移动。

  • 如果兔子和乌龟在同一个节点上，则返回，因为我们已经找到了链表环路。

  • 否则，从步骤 2 开始。

上述算法的伪代码

tortoise := headNode
hare := headNode
foreach:
   if hare == end
      return 'There is No Loop Found.'
   hare := hare.next
   if hare == end
      return 'No Loop Found'
   hare = hare.next
   tortoise = tortoise.next
   if hare == tortoise
      return 'Cycle Detected'

更新日期：05-Feb-2021

515 次浏览

开启你的 职业生涯

完成课程获得认证

开始
广告