線形データ構造のサイクルを検出するためのフロイドサイクル検出アルゴリズム

フロイドサイクルは、特定の単一リンクリスト内のサイクルを検出するためのサイクル検出アルゴリズムの1つです。

フロイドサイクルアルゴリズムでは、最初に先頭を指す2つのポインターがあります。うさぎとカメの話では、うさぎはカメの2倍の速さで動き、うさぎが小道の終わりに到達するたびに、カメは小道の真ん中に到達します。

アルゴリズム

• リストのヘッドノードでHareとTortoiseを初期化します。

• 最初、うさぎは亀の2倍の速さで動きます。

• うさぎと亀の両方を動かして、うさぎがリンクリストの最後に到達したかどうかを確認し、リストにループがないので戻ってください。

• そうでなければ、HareとTortoiseの両方が前進します。

• HareとTortoiseが同じノードにある場合は、リストサイクルが見つかったので、戻ります。

• それ以外の場合は、手順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'