Detaillierte Erläuterung der Schritte zum Auffinden des Eintragsknotens in der verknüpften Liste mithilfe von PHP

Dieses Mal werde ich Ihnen eine detaillierte Erklärung der Schritte geben, um den Einstiegsknoten in der Mitte der verknüpften Liste mit PHP zu finden. Was sind die Vorsichtsmaßnahmen, um den Einstiegsknoten in der Mitte zu finden? Verknüpfte Liste mit PHP Hier ist ein praktischer Fall, schauen wir uns das an.

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

Ich glaube, Sie haben die Methode gemeistert, nachdem Sie den Fall in diesem Artikel gelesen haben Weitere spannende Dinge finden Sie unter php Weitere verwandte Artikel auf der chinesischen Website!

Empfohlene Lektüre:

PHP-Codefreigabe zum Drucken von Binärbäumen von oben nach unten

Detaillierte Erläuterung der Schritte zum Drucken von PHP Binärbäume in Z-förmiger Reihenfolge

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