弗洛伊德環路檢測演算法，用於檢測線性資料結構中的環路

弗洛伊德環路是環路檢測演算法之一，用於檢測給定的單向連結串列中的環路。

在弗洛伊德環路演算法中，我們具有兩個指標，最初指向頭節點。在兔子和烏龜的故事中，兔子移動速度是烏龜的兩倍，每當兔子到達路徑末尾時，烏龜就會到達路徑中間。

演算法

  • 將兔子和烏龜初始化為連結串列的頭節點。

  • 最初，兔子的移動速度是烏龜的兩倍。

  • 將兔子和烏龜都向前移動，如果兔子到達連結串列的末尾，則返回，因為連結串列中沒有迴圈。

  • 否則，兔子和烏龜都會向前移動。

  • 如果兔子和烏龜在同一個節點上，則返回，因為我們已經找到了連結串列環路。

  • 否則，從步驟 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 次瀏覽

開啟你的 職業生涯

完成課程獲得認證

開始
廣告