이 글의 내용은 PHP에서 링 연결 리스트를 사용하여 링의 진입 노드(코드 예제)를 찾는 방법에 대한 것입니다. 필요한 친구들이 참고하면 도움이 될 것입니다. 당신.
연결된 리스트가 있고 링이 포함되어 있으면 연결리스트에서 링의 진입 노드를 찾고, 그렇지 않으면 null을 출력합니다.
1 연결리스트의 마지막에서 k번째 노드를 찾아 연결리스트를 입력합니다. , 연결된 리스트 k 노드에서 두 번째 노드를 출력합니다. 첫 번째 포인터는 k 번째 노드에 도달하기 위해 (k-1) 단계를 수행합니다. 두 포인터는 동시에 뒤로 이동합니다. 첫 번째 노드가 끝에 도달하면 두 번째 노드는 아래쪽에서 k 번째 노드에 위치합니다.
2. 원리는 위와 비슷합니다. 두 개의 포인터를 정의합니다. 하나는 매번 두 단계를 수행하는 빠른 포인터이고 다른 하나는 두 개가 만날 때 가정합니다. 링의 길이는 n 노트입니다. 느린 포인터는 x 단계를 수행하고 빠른 포인터는 2x 단계를 수행합니다. 2x=x+kn; 노드, 느린 포인터는 원래 위치에서 이동하지 않으며 둘은 하나를 수행합니다. 두 사람이 다시 만날 때 그들은 링의 입구에 있습니다. 링을 곧게 펴는 것을 상상해 보세요. 밑에서 k번째 노드와 매우 유사합니다
slow fast while 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 slow return null
<?php 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!