PHP implementiert die Suche nach dem Eintrittsknoten des Rings in der verknüpften Liste

In diesem Artikel wird die PHP-Implementierung erläutert, um den Eingangsknoten des Rings in der verknüpften Liste zu finden.

Eine verknüpfte Liste enthält einen Ring. Suchen Sie bitte den Eingangsknoten des Rings in der verknüpften Liste.

Lösungsideen

Der erste Schritt besteht darin, den Schnittpunkt im Ring zu finden. Verwenden Sie p1 und p2, um jeweils auf den Kopf der verknüpften Liste zu zeigen. p1 macht jeweils einen Schritt und p2 macht jedes Mal zwei Schritte, bis p1==p2 den Schnittpunkt im Ring findet.

Der zweite Schritt besteht darin, den Eingang zum Ring zu finden. In Fortsetzung des vorherigen Schritts beträgt die Anzahl der von p2 übergebenen Knoten 2x und die Anzahl der von p1 übergebenen Knoten x. Angenommen, es gibt n Knoten im Ring und p2 geht einen Kreis mehr als p1 , also 2x=n+x; n =x; Es ist ersichtlich, dass p1 tatsächlich die Anzahl der Schritte eines Rings annimmt und p2 dann auf den Kopf der verknüpften Liste zeigt p2 macht einen Schritt nach dem anderen, bis p1==p2; zu diesem Zeitpunkt zeigt p1 auf den Eingang des Rings. (Ich verstehe immer noch nicht viel)

Implementierungscode

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

In diesem Artikel wird die PHP-Implementierung erläutert, um den Einstiegsknoten des Rings in der verknüpften Liste zu finden. Für weitere verwandte Inhalte zahlen Sie bitte Aufmerksamkeit auf die chinesische PHP-Website.

Verwandte Empfehlungen:

So implementieren Sie die PHP-Nginx-Echtzeitausgabe

Verarbeitungsmethode der PHP-Klasse SoapClient nicht gefunden

So implementieren Sie die MongoDB-Singleton-Modus-Operationsklasse in PHP

Das obige ist der detaillierte Inhalt vonPHP implementiert die Suche nach dem Eintrittsknoten des Rings in der verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!