PHP實(shí)現(xiàn)找出鏈表中環(huán)的入口節(jié)點(diǎn)

本文實(shí)例講述了PHP實(shí)現(xiàn)找出鏈表中環(huán)的入口節(jié)點(diǎn)。分享給大家供大家參考，具體如下：

問(wèn)題

一個(gè)鏈表中包含環(huán)，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)。

解決思路

第一步，找環(huán)中相匯點(diǎn)。分別用p1，p2指向鏈表頭部，p1每次走一步，p2每次走二步，直到p1==p2找到在環(huán)中的相匯點(diǎn)。
第二步，找環(huán)的入口。接上步，當(dāng)p1==p2時(shí)，p2所經(jīng)過(guò)節(jié)點(diǎn)數(shù)為2x,p1所經(jīng)過(guò)節(jié)點(diǎn)數(shù)為x,設(shè)環(huán)中有n個(gè)節(jié)點(diǎn),p2比p1多走一圈有2x=n+x; n=x;可以看出p1實(shí)際走了一個(gè)環(huán)的步數(shù)，再讓p2指向鏈表頭部，p1位置不變，p1,p2每次走一步直到p1==p2; 此時(shí)p1指向環(huán)的入口。（還沒(méi)怎么懂）

實(shí)現(xiàn)代碼

?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;
}

更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《php程序設(shè)計(jì)算法總結(jié)》、《php字符串(string)用法總結(jié)》、《PHP數(shù)組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結(jié)》及《PHP數(shù)學(xué)運(yùn)算技巧總結(jié)》

希望本文所述對(duì)大家PHP程序設(shè)計(jì)有所幫助。