フロイドのカメとHareアルゴリズム:リンケージリストにおけるサイクルの発見

今日のalgorithm リンクリストのサイクル数です.

Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

例えば、入力がhead = [1, 3, 2, 5] and pos = 1 , リンクリストは次のようになります.

この問題はいくつかの異なる方法で解決できる.その1つはハッシュまたはセットを持ち、すべてのノードを監視します.ノードが既に見られるならば、あなたはそれがサイクルであるということを知っています.
出会ったFloyd's Cycle Detection Algorithm , また、フロイドの亀とハレアルゴリズムとして知られています.アルゴリズムの背後にあるアイデアは、リンクリストの2つのポインターを持っている場合、1つが他の(カメ)より2倍速く(Hare)を移動する場合、それらが交差する場合、リンクリスト内のサイクルがあります.彼らが交差しないならば、サイクルがありません.
このポストでは、この問題の解決方法を説明します.

亀とウサギのサイクルを見つける

この問題では、サイクルがあるかどうかのブール値を返すように求められます.リンクリストの先頭を与えられ、各ノードは値を持っています(.val ) で次のノードを見つけることができます.next .
まず最初にやることはhead が存在し、head.next が存在する.どちらも存在しないならば、サイクルはありません.

function hasCycle(head) {
  if (!head || !head.next) {
        return false
  }
  //...
}

次に、低速で高速なポインタを開始します.遅いポインタtortoise , は先頭のノードで開始する.高速ポインタhare , ヘッドで、一歩先を開始します.次.

function hasCycle(head) {
  if (!head || !head.next) {
        return false
  }
  let tortoise = head;
  let hare = head.next;

  //...
}

現在、HareがまだNULLでないノードを指している間、次のノードがまだNULLでない限り、我々は物事をチェックし続けます.したがって、これはwhileループを持つ良い場所です.

function hasCycle(head) {
  if (!head || !head.next) {
        return false
  }
  let tortoise = head;
  let hare = head.next;

  while (hare && hare.next) {
    //...
  }
  //...
}

whileループの中で、最初にするのはカメとウサギが同じノードを指しているかどうかをチェックすることです.彼らがそうであるならば、それはサイクルですtrue .

function hasCycle(head) {
  if (!head || !head.next) {
        return false
  }
  let tortoise = head;
  let hare = head.next;

  while (hare && hare.next) {
    if (tortoise === hare) {
      return true;
    }
    //...
  }
  //...
}

さもなければ、カメとウサギを動かします.カメは一度に1つのノードを動かします、そして、ウサギは同時に2つのノードを動かします.

function hasCycle(head) {
  if (!head || !head.next) {
        return false
  }
  let tortoise = head;
  let hare = head.next;

  while (hare && hare.next) {
    if (tortoise === hare) {
      return true;
    }
    tortoise = tortoise.next;
    hare = hare.next.next;
  }
  //...
}

最後に、whileループがhare //hare.next がNULLであれば、これまでのサイクルは見つけられなかったので、false .

function hasCycle(head) {
  if (!head || !head.next) {
        return false
  }
  let tortoise = head;
  let hare = head.next;

  while (hare && hare.next) {
    if (tortoise === hare) {
      return true;
    }
    tortoise = tortoise.next;
    hare = hare.next.next;
  }
  return false;
}

どのように動作するかを示す

このアルゴリズムを説明するのを助けるために、いくつかの非常に関連するclipartを使用します.リンクリストから始めましょう.ウサギが頭から始まる間、亀は頭から始まります.次.

ウサギとウサギから.次に両方ともNULLではないので、whileループに入ります.カメとウサギはお互いに等しくないので、私たちは両方とも彼らを動かします.カメは1つの場所に移動し、ウサギは2つのスポットを移動します.

whileループはまだtrueです.また、亀とウサギは互いに等しくない.我々は、1つのカメを移動し、2つのノード上のウサギを移動します.

whileループはまだ本当ですが、今回は亀とウサギはお互いに等しいです.これはサイクルが見つかったことを意味するので、真を返します.
--
コメントで私に任意の質問や代替アプローチを残してお気軽に!