本文實例講述了PHP實現找出鏈表中環的入口節點。分享給大家供大家參考，具體如下：
問題
一個鏈表中包含環，請找出該鏈表的環的入口結點。
解決思路
第一步，找環中相匯點。分別用p1，p2指向鏈表頭部，p1每次走一步，p2每次走二步，直到p1==p2找到在環中的相匯點。
第二步，找環的入口。接上步，當p1==p2時，p2所經過節點數為2x,p1所經過節點數為x,設環中有n個節點,p2比p1多走一圈有2x=n+x; n=x;可以看出p1實際走了一個環的步數，再讓p2指向鏈表頭部，p1位置不變，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程序設計算法總結》、《php字符串(string)用法總結》、《PHP數組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結》及《PHP數學運算技巧總結》
希望本文所述對大家PHP程序設計有所幫助。
您可能感興趣的文章:- PHP實現雙鏈表刪除與插入節點的方法示例
- php實現單鏈表的實例代碼
- PHP 雙鏈表(SplDoublyLinkedList)簡介和使用實例
- PHP小教程之實現雙向鏈表
- php鏈表用法實例分析
- PHP中模擬鏈表和鏈表的基本操作示例
- PHP實現的基于單向鏈表解決約瑟夫環問題示例
- PHP實現單鏈表翻轉操作示例
- php 數據結構之鏈表隊列
- PHP基于雙向鏈表與排序操作實現的會員排名功能示例
- PHP獲取鏈表中倒數第K個節點的方法
