Explanation of knowledge related to PHP implementation of finding the entry node 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 in need can refer to the following

Examples of this article Use PHP to find the entry node of the ring in the linked list. Share it with everyone for your reference, the details are as follows:

Question

A linked list contains a ring, please find the entrance of the ring in the linked list Node.

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

Articles you may be interested in:

PHP implements image processing tools that can add watermarks and generate thumbnails_php skills

##PHP Explanation of the method of printing a binary tree in zigzag order

Explanation of the method of obtaining a binary tree image with PHP

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