PHP implements finding the entry node of the ring in the linked list

This article explains PHP implementation to find the entry node of the ring in the linked list.

A linked list contains a ring, please find the entry node of the ring in the linked list.

Solution ideas

The first step is to find the intersection point in the ring. Use p1 and p2 to point to the head of the linked list respectively. p1 takes one step each time and p2 takes two steps each time until p1==p2 finds the intersection point in the ring.

The second step is to find the entrance to the ring. Continuing from the previous step, when p1==p2, the number of nodes passed by p2 is 2x, and the number of nodes passed by p1 is x. Assume there are n nodes in the ring, and p2 walks one more circle than p1, so 2x=n x; n=x ; It can be seen that p1 actually takes the number of steps of a ring, and then lets p2 point to the head of the linked list. The position of p1 remains unchanged. p1 and p2 take one step at a time until p1==p2; At this time, p1 points to the entrance of the ring. (I still don’t understand it very well)

Implementation code

/*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; 
}

This article explains the PHP implementation of finding the entry node of the ring in the linked list. For more related content, please pay attention to the PHP Chinese website.

Related recommendations:

php nginx real-time output implementation method

PHP Class SoapClient not found processing method

How to implement the mongoDB singleton mode operation class in php

The above is the detailed content of PHP implements finding the entry node of the ring in the linked list. For more information, please follow other related articles on the PHP Chinese website!