Explication des connaissances liées à l'implémentation PHP de la recherche du nœud d'entrée de l'anneau dans la liste chaînée

Cet article présente principalement l'implémentation PHP pour trouver le nœud d'entrée de l'anneau dans la liste chaînée, impliquant la traversée, la recherche, le calcul et d'autres compétences opérationnelles associées de PHP pour la liste chaînée circulaire. Les amis dans le besoin peuvent se référer à ce qui suit <.>

Question

Idée de solution

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 grand chose)

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

Implémentation PHP d'outils de traitement d'images pouvant ajouter des filigranes et générer des compétences thumbnails_php

Explication de la façon dont PHP imprime les arbres binaires en zigzag

Explication de la façon dont PHP obtient les images d'arbres binaires

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!