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 학습: 두 연결리스트의 첫 번째 공통 노드 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!