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ì)有所幫助。
- PHP實(shí)現(xiàn)雙鏈表刪除與插入節(jié)點(diǎn)的方法示例
- php實(shí)現(xiàn)單鏈表的實(shí)例代碼
- PHP 雙鏈表(SplDoublyLinkedList)簡(jiǎn)介和使用實(shí)例
- PHP小教程之實(shí)現(xiàn)雙向鏈表
- php鏈表用法實(shí)例分析
- PHP中模擬鏈表和鏈表的基本操作示例
- PHP實(shí)現(xiàn)的基于單向鏈表解決約瑟夫環(huán)問(wèn)題示例
- PHP實(shí)現(xiàn)單鏈表翻轉(zhuǎn)操作示例
- php 數(shù)據(jù)結(jié)構(gòu)之鏈表隊(duì)列
- PHP基于雙向鏈表與排序操作實(shí)現(xiàn)的會(huì)員排名功能示例
- PHP獲取鏈表中倒數(shù)第K個(gè)節(jié)點(diǎn)的方法
相關(guān)文章
php中數(shù)組去重的小例子，供初學(xué)者參考2013-02-02
php基于dom實(shí)現(xiàn)的圖書(shū)xml格式數(shù)據(jù)示例
這篇文章主要介紹了php基于dom實(shí)現(xiàn)的圖書(shū)xml格式數(shù)據(jù),結(jié)合實(shí)例形式分析了php數(shù)組轉(zhuǎn)換xml格式數(shù)據(jù)的相關(guān)操作技巧,需要的朋友可以參考下2017-02-02
這篇文章主要介紹了php中opendir函數(shù)用法,以實(shí)例形式詳細(xì)講述了opendir函數(shù)打開(kāi)目錄的用法及相關(guān)的注意事項(xiàng),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2014-11-11
php防止sql注入之過(guò)濾分頁(yè)參數(shù)實(shí)例
這篇文章主要介紹了php防止sql注入中過(guò)濾分頁(yè)參數(shù)的方法,實(shí)例展示了針對(duì)分頁(yè)參數(shù)的數(shù)值判斷問(wèn)題,是非常具有實(shí)用價(jià)值的技巧,需要的朋友可以參考下2014-11-11
這篇文章主要介紹了php線性表的入棧與出棧,實(shí)例分析了php操作線性表的入棧與出棧的相關(guān)技巧,需要的朋友可以參考下2015-06-06
這篇文章主要介紹了php封裝的page分頁(yè)類,結(jié)合完整實(shí)例形式分析了php數(shù)值運(yùn)算與字符串操作實(shí)現(xiàn)分頁(yè)功能的相關(guān)技巧,需要的朋友可以參考下2016-10-10
POST一個(gè)JSON格式的數(shù)據(jù)給Restful服務(wù)實(shí)例詳解
這篇文章主要介紹了POST一個(gè)JSON格式的數(shù)據(jù)給Restful服務(wù)實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-04-04
清除空格的方法是不安全的,部分原因是因?yàn)樽址械目崭穹浅６?例如 addslashes的問(wèn)題在 于黑客 可以用0xbf27來(lái)代替單引號(hào)2012-01-01
ThinkPHP中的Page類能輕松實(shí)現(xiàn)查詢內(nèi)容分頁(yè)的實(shí)現(xiàn)，本文小總結(jié)了一下關(guān)于學(xué)習(xí)過(guò)程中對(duì)Page類的使用方法。2014-05-05
php的instanceof和判斷閉包Closure操作示例
這篇文章主要介紹了php的instanceof和判斷閉包Closure操作,結(jié)合實(shí)例形式分析了PHP使用instanceof判斷類實(shí)例以及判斷閉包Closure相關(guān)操作技巧,需要的朋友可以參考下2020-01-01