The content of this article is about how to find the entry node (code example) of a ring in a linked list in PHP. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you. Helps.
Given a linked list, if it contains a ring, please find the entry node of the ring in the linked list, otherwise, output null
1. Find the k-th node from the bottom of the linked list and enter one Linked list, output the k-th node from the last in the linked list. The first pointer takes (k-1) steps to reach the k-th node. The two pointers move backward at the same time. When the first node reaches the end, the second node is located at the k-th node from the bottom.
2. The principle is a bit like the above. Define two pointers, one is the fast pointer that takes two steps each time, and the other is the slow pointer that takes one step each time. When the two meet, assume the length of the ring For n nodes, the slow pointer takes x steps, and the fast pointer takes 2x steps. 2x=x kn; #3. The fast pointer returns to the head node, and the slow pointer does not move at the original position. The two take one step each time. When the two meet again, they are at the entrance of the ring; imagine straightening the ring, and the kth from the bottom The nodes are very similar
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* } } }
The above is the detailed content of How to find the entry node of a ring with a ring linked list in PHP (code example). For more information, please follow other related articles on the PHP Chinese website!