Apprentissage PHP : Trouver le premier nœud commun de deux listes chaînées

L'éditeur de cet article vous apprendra à utiliser PHP pour trouver le premier nœud commun de deux listes liées. Il a une certaine valeur de référence. Les amis intéressés peuvent y jeter un œil.

Entrez deux listes chaînées et trouvez leur premier nœud commun
1 Si deux listes chaînées ont des nœuds communs, alors il est inévitable que les queues soient communes
Trouver la liste chaînée 1. longueur de la liste chaînée 2, trouvez la longueur de la liste chaînée 2, soustrayez la liste chaînée courte de la liste chaînée longue pour obtenir une valeur n
3. La liste chaînée longue se déplace d'abord de n pas, puis les deux listes chaînées se déplacent en même temps
4. Deux listes chaînées Le point d'intersection est le premier nœud public

list1 list2
len1 len2

if len1 > len2
    n=len1-len2
    for i=0;i<n;i++
        list1=list1->next
else
    n=len2-len1
    for i=0;i<n;i++
        list2=list2->next

while list1!=null
    if list1==list2 
        return list1
    list1=list1->next
    list2=list2->next
return null

<?php
class Node{
        public $data;
        public $next;
        public function __construct($data=""){
                $this->data=$data;
        }   
}
//构造一个链表
$linkList1=new Node();
$linkList1->next=null;
$temp=$linkList1;

$node1=new Node(1);
$temp->next=$node1;
$temp=$node1;

$node2=new Node(2);
$temp->next=$node2;
$temp=$node2;

$node3=new Node(3);
$temp->next=$node3;
$temp=$node3;

$node4=new Node(4);
$temp->next=$node4;
$temp=$node4;

$node5=new Node(5);
$temp->next=$node5;
$node5->next=null;

//构造一个和上面有公共结点的链表
$linkList2=new Node();
$linkList2->next=null;
$temp=$linkList2;

$node7=new Node(7);
$temp->next=$node7;
$node7->next=$node4;//链向上面链表的第四个结点


var_dump($linkList1);
var_dump($linkList2);
$commonNode=FindFirstCommonNode($linkList1,$linkList2);
var_dump($commonNode);
//找第一个公共结点
function FindFirstCommonNode($pHead1, $pHead2){
        //链表1的长度
        $len1=0;
        $temp=$pHead1->next;
        while($temp!=null){
                $temp=$temp->next;
                $len1++;
        }
        //链表2的长度
        $len2=0;
        $temp=$pHead2->next;
        while($temp!=null){
                $temp=$temp->next;
                $len2++;
        }
        $list1=$pHead1->next;
        $list2=$pHead2->next;
        //长的链表先走n步
        if($len1 > $len2){
                $n=$len1-$len2;
                for($i=0;$i<$n;$i++){
                        $list1=$list1->next;
                }
        }else{
                $n=$len2-$len1;
                for($i=0;$i<$n;$i++){
                        $list2=$list2->next;
                }

        }
        //两个链表长度一致，同时走，第一个相同的点就是第一个公共结点
        while($list1!=null){
                if($list1==$list2){
                        return $list1;
                }
                $list1=$list1->next;
                $list2=$list2->next;
        }
        return null;
}

object(Node)#1 (2) {
  ["data"]=>
  string(0) ""
  ["next"]=>
  object(Node)#2 (2) {
    ["data"]=>
    int(1)
    ["next"]=>
    object(Node)#3 (2) {
      ["data"]=>
      int(2)
      ["next"]=>
      object(Node)#4 (2) {
        ["data"]=>
        int(3)
        ["next"]=>
        object(Node)#5 (2) {
          ["data"]=>
          int(4)
          ["next"]=>
          object(Node)#6 (2) {
            ["data"]=>
            int(5)
            ["next"]=>
            NULL
          }
        }
      }
    }
  }
}
object(Node)#7 (2) {
  ["data"]=>
  string(0) ""
  ["next"]=>
  object(Node)#8 (2) {
    ["data"]=>
    int(7)
    ["next"]=>
    object(Node)#5 (2) {
      ["data"]=>
      int(4)
      ["next"]=>
      object(Node)#6 (2) {
        ["data"]=>
        int(5)
        ["next"]=>
        NULL
      }
    }
  }
}
object(Node)#5 (2) {
  ["data"]=>
  int(4)
  ["next"]=>
  object(Node)#6 (2) {
    ["data"]=>
    int(5)
    ["next"]=>
    NULL
  }
}

Tutoriels associés : Tutoriel vidéo PHP

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!