PHPを使用してリンクリスト内のエントリノードを見つける手順の詳細な説明

今回は、PHPでリンクリストの途中にあるエントリノードを見つける手順について詳しく説明します。 PHPでリンクリストの途中にあるエントリノードを見つけるための注意点は何ですか。実際のケースですので、見てみましょう。

質問

リンクリストにリングが含まれています。リンクリストでリングのエントリノードを見つけてください。

解決策のアイデア

最初のステップは、リング内の交点を見つけることです。 p1 と p2 を使用して、p1==p2 がリング内の交点を見つけるまで、p1 は毎回 1 ステップ、p2 は毎回 2 ステップを実行します。
2 番目のステップは、リングの入り口を見つけることです。前のステップからの続きで、p1==p2 の場合、p2 が通過するノードの数は 2x、p1 が通過するノードの数は x であり、リング内に n 個のノードがあり、p2 は p1 よりも 1 つ多く円を歩きます。 , so 2x=n+x; n =x; p1 が実際にリングのステップ数を取得し、p2 が p1 の位置を変更しないことがわかります。 p2 は p1==p2 まで一歩ずつ進みます。このとき、p1 はリングの入り口を指します。 (まだよく理解できていません)

コードの実装

<?php
/*class ListNode{
  var $val;
  var $next = NULL;
  function construct($x){
    $this->val = $x;
  }
}*/
function EntryNodeOfLoop($pHead)
{
  if($pHead == null || $pHead->next == null)
    return null;
  $p1 = $pHead;
  $p2 = $pHead;
  while($p2!=null && $p2->next!=null){
    $p1 = $p1->next;
    $p2 = $p2->next->next;
    if($p1 == $p2){
      $p2 = $pHead;
      while($p1!=$p2){
        $p1 = $p1->next;
        $p2 = $p2->next;
      }
      if($p1 == $p2)
        return $p1;
    }
  }
  return null;
}

この記事の事例を読んで、この方法を習得したと思います。さらに興味深い情報については、 の他の関連記事に注目してください。 PHPの中国語サイトです！

推奨書籍:

バイナリ ツリーを上から下に出力するための PHP コード共有

PHP が Z 字型の順序を使用してバイナリ ツリーを出力する手順の詳細な説明

以上がPHPを使用してリンクリスト内のエントリノードを見つける手順の詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。