この記事では主に、リンク リスト内のリングのエントリ ノードを見つけるための 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 ajaxでノードを動的に追加してもクリックイベントをトリガーできない 方法それを解決してください
イベントバブリング、イベント委任、jQuery要素ノード操作についての簡単な説明
以上がリンクリスト内のリングのエントリノードインスタンスを見つけるためのPHP実装の詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。