PHP实现找出链表中环的入口节点

时间:2022-01-28 16:06:17

本文实例讲述了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指向环的入口。(还没怎么懂)

实现代码

  1. <?php 
  2. /*class ListNode{ 
  3.   var $val; 
  4.   var $next = NULL; 
  5.   function __construct($x){ 
  6.     $this->val = $x; 
  7.   } 
  8. }*/ 
  9. function EntryNodeOfLoop($pHead
  10.   if($pHead == null || $pHead->next == null) 
  11.     return null; 
  12.   $p1 = $pHead
  13.   $p2 = $pHead
  14.   while($p2!=null && $p2->next!=null){ 
  15.     $p1 = $p1->next; 
  16.     $p2 = $p2->next->next; 
  17.     if($p1 == $p2){ 
  18.       $p2 = $pHead
  19.       while($p1!=$p2){ 
  20.         $p1 = $p1->next; 
  21.         $p2 = $p2->next; 
  22.       } 
  23.       if($p1 == $p2
  24.         return $p1
  25.     } 
  26.   } 
  27.   return null; 

希望本文所述对大家PHP程序设计有所帮助。