Detailed explanation of PHP implementation to find the entry node instance of the ring in the linked list

This article mainly introduces the PHP implementation to find the entry node of the ring in the linked list, involving PHP's traversal, search, calculation and other related operating skills for the circular linked list. Friends who need it can refer to it. I hope it can help everyone.

Question

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 don’t understand much yet)

Implementation code

##

<?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;
}

Related recommendations:

JQuery node traversal method summary

jQuery ajax dynamically added node cannot trigger click event how to solve it

A brief discussion on event bubbling , event delegation, jQuery element node operation

The above is the detailed content of Detailed explanation of PHP implementation to find the entry node instance of the ring in the linked list. For more information, please follow other related articles on the PHP Chinese website!