PHP中如何查找兩個鏈表的第一個公共結點

小編給大家分享一下PHP中如何查找兩個鏈表的第一個公共結點，希望大家閱讀完這篇文章后大所收獲，下面讓我們一起去探討吧！

輸入兩個鏈表，找出它們的第一個公共結點
1.兩個單鏈表，有公共結點，那么必然，尾部公用
2.找出鏈表1的長度，找出鏈表2的長度，長的鏈表減去短的鏈表得出一個n值
3.長的鏈表先走n步，兩個鏈表再同時移動
4.兩個鏈表相交點就是第一個公共結點

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

看完了這篇文章，相信你對PHP中如何查找兩個鏈表的第一個公共結點有了一定的了解，想了解更多相關知識，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！