Detailed explanation of the steps to find the entry node in the linked list using PHP

This time I will bring you a detailed explanation of the steps to find the entry node in the linked list with PHP. What are the precautions for PHP to find the entry node in the linked list. The following is a practical case, let's take a look.

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

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

I believe you have mastered the method after reading the case in this article. For more exciting things, please pay attention to php Other related articles on the Chinese website!

Recommended reading:

PHP implements code sharing for printing binary trees from top to bottom

Detailed explanation of the steps for PHP to print binary trees in Z-shaped order

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