この記事では主に、リンク リスト内のリングのエントリ ノードを見つけるための 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 中国語 Web サイトの他の関連記事を参照してください。