Explication détaillée de la fusion de deux listes chaînées triées en PHP

Cet article présente principalement la méthode de fusion de deux listes chaînées triées en PHP, impliquant les compétences opérationnelles associées de PHP en matière de parcours, de jugement, de tri et d'autres listes chaînées. J'espère que cela pourra aider tout le monde.

Problème

Entrer deux listes chaînées croissantes de manière monotone et sortir la liste chaînée synthétisée des deux listes chaînées. Bien sûr, nous avons besoin de la liste chaînée synthétisée. la liste chaînée pour satisfaire Monotone ne diminue pas la règle.

Solution

Tri par fusion simple. Étant donné que les deux tableaux augmentent de manière inhérente, prenez simplement la plus petite partie des deux tableaux à chaque fois.

Code d'implémentation

<?php
/*class ListNode{
 var $val;
 var $next = NULL;
 function __construct($x){
  $this->val = $x;
 }
}*/
function Merge($pHead1, $pHead2)
{
 if($pHead1 == NULL)
  return $pHead2;
 if($pHead2 == NULL)
  return $pHead1;
 $reHead = new ListNode();
 if($pHead1->val < $pHead2->val){
  $reHead = $pHead1;
  $pHead1 = $pHead1->next;
 }else{
  $reHead = $pHead2;
  $pHead2 = $pHead2->next;
 }
 $p = $reHead;
 while($pHead1&&$pHead2){
  if($pHead1->val <= $pHead2->val){
   $p->next = $pHead1;
   $pHead1 = $pHead1->next;
   $p = $p->next;
  }
  else{
   $p->next = $pHead2;
   $pHead2 = $pHead2->next;
   $p = $p->next;
  }
 }
 if($pHead1 != NULL){
  $p->next = $pHead1;
 }
 if($pHead2 != NULL)
  $p->next = $pHead2;
 return $reHead;
}

Recommandations associées :

Structure de données JavaScript, partage d'exemple de liste chaînée unique et de liste chaînée circulaire

Méthode PHP pour obtenir le nœud K à partir du dernier dans l'exemple de partage de liste chaînée

PHP Double Exemple détaillé de liste chaînée

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!