Explication détaillée des étapes pour trouver le nœud d'entrée dans la liste chaînée en utilisant PHP

Cette fois, je vais vous donner une explication détaillée des étapes pour trouver le nœud d'entrée au milieu de la liste chaînée avec PHP Quelles sont les précautions pour trouver le nœud d'entrée au milieu de la. liste chaînée avec PHP Voici un cas pratique, jetons un oeil.

Question

Une liste chaînée contient un anneau, veuillez trouver le nœud d'entrée de l'anneau dans la liste chaînée.

Idée de solution

La première étape consiste à trouver le point d'intersection dans l'anneau. Utilisez p1 et p2 pour pointer respectivement vers la tête de la liste chaînée. p1 fait un pas à chaque fois et p2 fait deux pas à chaque fois jusqu'à ce que p1==p2 trouve le point d'intersection dans l'anneau.
La deuxième étape consiste à trouver l'entrée du ring. Dans la continuité de l'étape précédente, lorsque p1 == p2, le nombre de nœuds passés par p2 est 2x et le nombre de nœuds passés par p1 est x Supposons qu'il y ait n nœuds dans l'anneau et que p2 parcourt un cercle de plus que p1. , donc 2x=n+x; n =x; On peut voir que p1 prend en fait le nombre d'étapes d'un anneau, puis laisse p2 pointer vers la tête de la liste chaînée. La position de p1 reste inchangée. p2 fait un pas à la fois jusqu'à ce que p1 == p2 à ce moment, p1 pointe vers l'entrée de l'anneau. (Je ne comprends pas encore)

Code d'implémentation

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

Je crois que vous maîtrisez la méthode après avoir lu le cas dans cet article, veuillez venir pour des informations plus intéressantes. Faites attention aux autres articles connexes sur le site Web chinois de php !

Lecture recommandée :

Partage de code PHP pour imprimer des arbres binaires de haut en bas

Explication détaillée des étapes d'impression de PHP arbres binaires dans l'ordre en forme de Z

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!