So finden Sie den ersten gemeinsamen Knoten zweier verknüpfter Listen in PHP (Codebeispiel)

In diesem Artikel erfahren Sie, wie Sie den ersten gemeinsamen Knoten (Codebeispiel) von zwei verknüpften Listen in PHP finden. Ich hoffe, dass er Ihnen helfen wird .

Geben Sie zwei verknüpfte Listen ein und finden Sie ihren ersten gemeinsamen Knoten

1. Zwei einfach verknüpfte Listen haben gemeinsame Knoten, daher ist es unvermeidlich, dass die Enden gemeinsam sind

2. Ermitteln Sie die Länge der verknüpften Liste 1, ermitteln Sie die Länge der verknüpften Liste 2, subtrahieren Sie die kurze verknüpfte Liste von der langen verknüpften Liste, um einen n-Wert zu erhalten

3. long Die verknüpfte Liste bewegt sich zunächst um n Schritte, und dann bewegen sich die beiden verknüpften Listen gleichzeitig

4. Der Schnittpunkt der beiden verknüpften Listen ist der erste gemeinsame Knoten
   

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

Verwandte Empfehlungen:

So finden Sie es heraus die verknüpfte Liste in PHP Der Eingangsknoten des Rings (Codebeispiel)

So geben Sie den k-ten Knoten aus der letzten verknüpften Liste in PHP aus (Codebeispiel)

Das obige ist der detaillierte Inhalt vonSo finden Sie den ersten gemeinsamen Knoten zweier verknüpfter Listen in PHP (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!