Erläuterung der Kenntnisse im Zusammenhang mit der PHP-Implementierung zum Finden des Eintrittsknotens 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 in Not können sich auf das Folgende beziehen

In diesem Artikel werden die Beispiele erläutert. Verwenden Sie PHP, um den Eintrittsknoten des Rings in der verknüpften Liste zu finden. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Frage

Eine verknüpfte Liste enthält einen Ring, bitte finden Sie den Eingang des Rings im verknüpften Listenknoten.

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

Artikel, die Sie interessieren könnten:

PHP-Implementierung von Bildverarbeitungstools, die Wasserzeichen hinzufügen und Miniaturansichten generieren können_php-Fähigkeiten

PHP Eine Erklärung der Methode zum Drucken eines Binärbaums in Zickzack-Reihenfolge

Eine Erklärung der Methode zum Erhalten eines Binärbaumbilds mit PHP

Das obige ist der detaillierte Inhalt vonErläuterung der Kenntnisse im Zusammenhang mit der PHP-Implementierung zum Finden des Eintrittsknotens des Rings in der verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!