How to find the entry node of a ring with a ring linked list in PHP (code example)

The content of this article is about how to find the entry node (code example) of a ring in a linked list in PHP. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you. Helps.

Given a linked list, if it contains a ring, please find the entry node of the ring in the linked list, otherwise, output null

1. Find the k-th node from the bottom of the linked list and enter one Linked list, output the k-th node from the last in the linked list. The first pointer takes (k-1) steps to reach the k-th node. The two pointers move backward at the same time. When the first node reaches the end, the second node is located at the k-th node from the bottom.

2. The principle is a bit like the above. Define two pointers, one is the fast pointer that takes two steps each time, and the other is the slow pointer that takes one step each time. When the two meet, assume the length of the ring For n nodes, the slow pointer takes x steps, and the fast pointer takes 2x steps. 2x=x kn; #3. The fast pointer returns to the head node, and the slow pointer does not move at the original position. The two take one step each time. When the two meet again, they are at the entrance of the ring; imagine straightening the ring, and the kth from the bottom The nodes are very similar

slow fast
while fast!=null && fast->next!=null
    slow=slow->next
    fast=fast->next->next
    if slow==fast
        fast=head
        while slow!=fast
            slow=slow->next
            fast=fast->next
        if slow==fast
            return slow
return null

<?php
class Node{
        public $data;
        public $next;
        public function __construct($data=""){
                $this->data=$data;
        }   
}
//构造一个带环的链表
$linkList=new Node();
$linkList->next=null;
$temp=$linkList;

$node1=new Node("111");
$temp->next=$node1;
$temp=$node1;

$node2=new Node("222");
$temp->next=$node2;
$temp=$node2;

$node3=new Node("333");
$temp->next=$node3;
$temp=$node3;

$node4=new Node("444");
$temp->next=$node4;
$node4->next=$node2;//尾结点指向第二个结点

function EntryNodeOfLoop($pHead){
        $slow=$pHead;
        $fast=$pHead;
        while($fast!=null && $fast->next!=null){
                $slow=$slow->next;//慢指针走一步
                $fast=$fast->next->next;//快指针走两步
                //快慢指针环内相遇
                if($slow==$fast){
                        //快指针回到头结点
                        $fast=$pHead;
                        //同一速度再同时走
                        while($slow!=$fast){
                                $slow=$slow->next;
                                $fast=$fast->next;
                        }   
                        //两个相遇的点一定是环的入口
                        if($slow==$fast){
                                return $fast;
                        }   
                }   
        }   
}
var_dump($linkList);
$result=EntryNodeOfLoop($linkList);
var_dump($result);

object(Node)#1 (2) {
  ["data"]=>  string(0) ""
  ["next"]=>  object(Node)#2 (2) {
    ["data"]=>    string(3) "111"
    ["next"]=>    object(Node)#3 (2) {
      ["data"]=>      string(3) "222"
      ["next"]=>      object(Node)#4 (2) {
        ["data"]=>        string(3) "333"
        ["next"]=>        object(Node)#5 (2) {
          ["data"]=>          string(3) "444"
          ["next"]=>
          *RECURSION*
        }
      }
    }
  }
}object(Node)#3 (2) {
  ["data"]=>  string(3) "222"
  ["next"]=>  object(Node)#4 (2) {
    ["data"]=>    string(3) "333"
    ["next"]=>    object(Node)#5 (2) {
      ["data"]=>      string(3) "444"
      ["next"]=>
      *RECURSION*
    }
  }
}

Related recommendations:

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

PHP implementation Circular linked list function

The above is the detailed content of How to find the entry node of a ring with a ring linked list in PHP (code example). For more information, please follow other related articles on the PHP Chinese website!