PHP学习之查找两个链表的第一个公共结点

发布:smiling　来源: PHP粉丝网　添加日期：2020-04-04 22:10:43　浏览: 评论：0　

本篇文章小编将带大家学习用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

  }

}