Explication détaillée de l'implémentation de PHP pour trouver l'instance de nœud d'entrée de l'anneau dans la liste chaînée

小云云
Libérer: 2023-03-19 14:46:02
original
1524 Les gens l'ont consulté

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 qui en ont besoin peuvent s'y référer. J'espère que cela pourra aider tout le monde.

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 toujours pas 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;
}
Copier après la connexion

Recommandations associées :

Résumé de la méthode de traversée des nœuds JQuery

jQuery ajax l'ajout dynamique de nœuds ne peut pas déclencher d'événements de clic

Une brève discussion sur les événements Bubbling, la délégation d'événements, les opérations de nœud d'élément jQuery

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!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal
À propos de nous Clause de non-responsabilité Sitemap
Site Web PHP chinois:Formation PHP en ligne sur le bien-être public,Aidez les apprenants PHP à grandir rapidement!