PHP實作找出鍊錶中環的入口節點

本篇講解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指向環的入口。 (還沒怎麼懂)

實作程式碼

/*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 nginx 即時輸出的實作方法

PHP Class SoapClient not found處理方法

php如何實作的mongoDB單例模式操作類別

#

以上是PHP實作找出鍊錶中環的入口節點的詳細內容。更多資訊請關注PHP中文網其他相關文章！