Detaillierte Erläuterung der PHP-Implementierung zum Auffinden der Eintrittsknoteninstanz des Rings in der verknüpften Liste

Dieser Artikel stellt hauptsächlich die PHP-Implementierung vor, um den Eintrittsknoten des Rings in der verknüpften Liste zu finden, einschließlich der Durchlauf-, Such-, Berechnungs- und anderen damit verbundenen Betriebsfähigkeiten von PHP für die zirkuläre verknüpfte Liste. Freunde, die sie benötigen, können darauf verweisen. Ich hoffe, es kann allen helfen.

Frage

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

Lösungsidee

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

<?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;
}

Verwandte Empfehlungen:

Zusammenfassung der JQuery-Knotendurchlaufmethode

Das dynamische Hinzufügen von Knoten durch jQuery Ajax kann keine Klickereignisse auslösen

Eine kurze Diskussion über Ereignisse, Bubbling, Ereignisdelegierung, jQuery-Elementknotenoperationen

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der PHP-Implementierung zum Auffinden der Eintrittsknoteninstanz des Rings in der verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!