So finden Sie den Eintrittsknoten eines Rings mit einer ringverknüpften Liste in PHP (Codebeispiel)

Der Inhalt dieses Artikels befasst sich damit, wie man den Einstiegsknoten (Codebeispiel) eines Rings mit einer Ringverknüpfungsliste findet. Ich hoffe, dass dies der Fall ist nützlich für Sie.

Wenn eine verknüpfte Liste einen Ring enthält, suchen Sie bitte den Eingangsknoten des Rings in der verknüpften Liste. Andernfalls geben Sie null aus.

1 Suchen Sie den k-ten Knoten aus Geben Sie unten in der verknüpften Liste eine verknüpfte Liste ein und geben Sie den k-ten Knoten vom letzten in der verknüpften Liste aus. Der erste Zeiger benötigt (k-1) Schritte, um den k-ten Knoten zu erreichen. Die beiden Zeiger bewegen sich gleichzeitig rückwärts. Wenn der erste Knoten das Ende erreicht, befindet sich der zweite Knoten am k-ten Knoten von unten .

2. Das Prinzip ist ein bisschen wie oben, einer ist der schnelle Zeiger, der jedes Mal zwei Schritte ausführt, und der andere ist der langsame Zeiger, der jedes Mal einen Schritt ausführt zwei treffen sich, nehmen Sie die Länge des Rings an. Für n Knoten benötigt der langsame Zeiger x Schritte, und der schnelle Zeiger kehrt zum Kopfknoten zurück Der Zeiger bewegt sich nicht an der ursprünglichen Position. Wenn die beiden sich wieder treffen, befinden sie sich am Eingang des Rings und der k-te Punkt ist sehr groß ähnlich

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

Verwandte Empfehlungen:

PHP-Implementierung, um den Eintrittsknoten des Rings in der verknüpften Liste zu finden

PHP Implementieren Sie die Funktion einer zirkulären verknüpften Liste

Das obige ist der detaillierte Inhalt vonSo finden Sie den Eintrittsknoten eines Rings mit einer ringverknüpften Liste in PHP (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!