PHP实现找出链表中环的入口节点 |
|
本文标签：PHP,链表,环,入口节点 本文实例讲述了PHP实现找出链表中环的入口节点 。分享给大家供大家参考，具体如下： 问题 一个链表中包含环，请找出该链表的环的入口结点 。 解决思路 第一步，找环中相汇点 。分别用p1，p2指向链表头部，p1每次走一步，p2每次走二步，直到p1==p2找到在环中的相汇点 。 实现代码
<?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程序设计有所帮助 。 您可能感兴趣的文章:
|
