リンクリスト内のリングのエントリノードインスタンスを見つけるための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;
}

関連推奨事項:

jQueryノードトラバーサル方法の概要

jQuery ajaxでノードを動的に追加してもクリックイベントをトリガーできない 方法それを解決してください

イベントバブリング、イベント委任、jQuery要素ノード操作についての簡単な説明

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