リンクリストからリングの入口ノードを見つけるPHP実装に関する知識の解説

この記事では主に、リンク リスト内のリングのエントリ ノードを見つけるための 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 の位置は変更されません。p1 と p2 はかかります。 one step at a time until 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 の説明二分木をジグザグに印刷する方法

PHPで二分木画像を取得する方法の説明

##

以上がリンクリストからリングの入口ノードを見つけるPHP実装に関する知識の解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。