Comment trouver le nœud d'entrée d'un anneau avec une liste chaînée d'anneaux en PHP (exemple de code)

Le contenu de cet article explique comment trouver le nœud d'entrée (exemple de code) d'un anneau avec une liste chaînée en anneau en PHP. J'espère que ce sera le cas. utile pour vous.

Étant donné une liste chaînée, si elle contient un anneau, veuillez trouver le nœud d'entrée de l'anneau dans la liste chaînée, sinon, sortez null

Trouvez le k-ème nœud du. en bas de la liste chaînée et entrez une liste chaînée, affichez le k-ème nœud du dernier dans la liste chaînée. Le premier pointeur prend (k-1) pas pour atteindre le k-ème nœud. Les deux pointeurs reculent en même temps. Lorsque le premier nœud atteint la fin, le deuxième nœud est situé au k-ème nœud à partir du bas. .

2. Le principe est un peu comme ci-dessus Définissez deux pointeurs, l'un est le pointeur rapide qui fait deux pas à chaque fois, et l'autre est le pointeur lent qui fait un pas à chaque fois. deux se rencontrent, supposons la longueur de l'anneau. Pour n nœuds, le pointeur lent fait x pas et le pointeur rapide prend 2x pas, 2x=x+kn ; le pointeur ne bouge pas à la position d'origine. Les deux font un pas à chaque fois. Lorsque les deux se rencontrent à nouveau, ils sont à l'entrée de l'anneau ; imaginez redresser l'anneau et le kth par le bas. Les nœuds sont très similaires

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

Recommandations associées :

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

Implémentation PHP pour trouver le nœud d'entrée de l'anneau dans la liste chaînée

PHP implémente la fonction de liste chaînée circulaire

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!