Implementation of PHP to Find the Entry Node of Ring in Linked List

In this paper, an example is given to find out the entry node of the ring in the linked list by PHP. Share it for your reference, as follows:

Problem

1 linked list contains rings, please find the entry node of the rings in the linked list.

Solutions

Step 1: Find the intersection point in the ring. Point to the head of the linked list with p1 and p2 respectively, p1 take one step at a time, and p2 take two steps at a time until p1==p2 finds the intersection point in the ring.
Step 2, find the entrance of the ring. In the following step, when p1==p2, the number of nodes passed by p2 is 2x, the number of nodes passed by p1 is x, and there are n nodes in the ring, and p2 travels one more lap than p1 with 2x=n+x; n = x; It can be seen that p1 actually takes one ring step, and then p2 points to the head of the linked list. The position of p1 remains unchanged, and p1 and p2 take one step at a time until p1==p2; At this point, p1 points to the entrance of the ring. (Haven't quite understood 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;
}

For more readers interested in PHP related contents, please check the special topics of this site: "PHP Data Structure and Algorithm Tutorial", "php Programming Algorithm Summary", "php String (string) Usage Summary", "PHP Array (Array) Operation Skills Complete Book", "PHP Common Traversal Algorithms and Skills Summary" and "PHP Mathematical Operation Skills Summary"

I hope this article is helpful to everyone's PHP programming.