服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - PHP教程 - PHP实现找出链表中环的入口节点

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

2019-10-25 12:51重口味AC PHP教程

这篇文章主要介绍了PHP实现找出链表中环的入口节点,涉及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指向环的入口。(还没怎么懂)

实现代码

  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程序设计有所帮助。

延伸 · 阅读

精彩推荐