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視訊教學

以上就是PHP學習之查詢兩個連結串列的第一個公共結點的詳細內容，更多請關注TW511.COM其它相關文章！