給一個鏈表，若其中包含環，請找出該鏈表的環的入口結點，否則，輸出null

1.找鏈表倒數第k個結點,輸入一個鏈表，輸出該鏈表中倒數第k個結點。第一個指針走(k-1)步，到達第k個節點,兩個指針同時往后移動，當第一個結點到達末尾的時候，第二個結點所在位置就是倒數第k個節點了

2.原理有點像上面的，定義兩個指針，一個是快指針每次走兩步，一個是慢指針每次走一步，當兩個相遇的時候，假設環的長度為n個結點，慢指針走x步，快指針走2x步，2x=x+kn ;x=kn; k暫時假定為1圈 ，也就是慢指針slow走了一個環的距離

3.快指針回到頭結點，慢指針原位置不動，兩個每次都是走一步，當兩個再次相遇的時候，就是在環入口；想象把環捋直，和倒數第k個結點很像了

slow fastwhile fast!=null fast- next!=null slow=slow- next fast=fast- next- next if slow==fast fast=head while slow!=fast slow=slow- next fast=fast- next if slow==fast return slowreturn null

 ?phphtml' target='_blank'>class Node{ public $data; public $next; public function __construct($data= ){ $this- data=$data;//構造一個帶環的鏈表$linkList=new Node();$linkList- next=null;$temp=$linkList;$node1=new Node( 111 $temp- next=$node1;$temp=$node1;$node2=new Node( 222 $temp- next=$node2;$temp=$node2;$node3=new Node( 333 $temp- next=$node3;$temp=$node3;$node4=new Node( 444 $temp- next=$node4;$node4- next=$node2;//尾結點指向第二個結點function EntryNodeOfLoop($pHead){ $slow=$pHead; $fast=$pHead; while($fast!=null $fast- next!=null){ $slow=$slow- next;//慢指針走一步 $fast=$fast- next- next;//快指針走兩步 //快慢指針環內相遇 if($slow==$fast){ //快指針回到頭結點 $fast=$pHead; //同一速度再同時走 while($slow!=$fast){ $slow=$slow- next; $fast=$fast- next; //兩個相遇的點一定是環的入口 if($slow==$fast){ return $fast;var_dump($linkList);$result=EntryNodeOfLoop($linkList);var_dump($result);

object(Node)#1 (2) { [ data ]= string(0)  [ next ]= object(Node)#2 (2) { [ data ]= string(3) 111  [ next ]= object(Node)#3 (2) { [ data ]= string(3) 222  [ next ]= object(Node)#4 (2) { [ data ]= string(3) 333  [ next ]= object(Node)#5 (2) { [ data ]= string(3) 444  [ next ]=  *RECURSION*}object(Node)#3 (2) { [ data ]= string(3) 222  [ next ]= object(Node)#4 (2) { [ data ]= string(3) 333  [ next ]= object(Node)#5 (2) { [ data ]= string(3) 444  [ next ]=  *RECURSION*}

相關推薦：

PHP實現找出鏈表中環的入口節點

PHP實現循環鏈表功能

以上就是php如何實現找出帶環鏈表的環的入口結點（代碼實例）的詳細內容，PHP教程

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。