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

yipeiwu_com6年前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指向环的入口。(还没怎么懂)

实现代码

<?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中$_SERVER使用说明

PHP编程中经常需要用到一些服务器的一些资料,特把$_SERVER的详细参数整理下,方便以后使用。 $_SERVER['PHP_SELF'] #当前正在执行脚本的文件名,与 docu...

php中的Base62类(适用于数值转字符串)

Base62类源码:复制代码 代码如下:class Base62 {    private $string = "vPh7zZwA2LyU4bGq5tcVf...

PHPwind整合最土系统用户同步登录实现方法

上次成功升级了最土商业版,接下来就是整合公司的社区网站,先说明一下我现在工作的地方是个地方社区网站,用的基础程序是PHPWind,我的任务就是让PHPWind和最土登录同步,领导也知道我...

php数组相加 array(“a”)+array(“b”)结果还是array(“a”)

在网上看到一道题: array("a")+array("b")的结果是___ A.array("a","b")B.array("b","a")C.array("b")D.array("a...

PHP中使用数组实现堆栈数据结构的代码

在堆栈中,最后压入的数据(进栈),将会被最先弹出(出栈)。 即在数据存储时采用“先进后出”的数据结构。 PHP中,将数组当做一个栈,主要是使用array_push()和array_pop...