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
- }
- }
Tags: PHP查找两个链表
推荐文章
热门文章
最新评论文章
- 写给考虑创业的年轻程序员(10)
- PHP新手上路(一)(7)
- 惹恼程序员的十件事(5)
- PHP邮件发送例子,已测试成功(5)
- 致初学者:PHP比ASP优秀的七个理由(4)
- PHP会被淘汰吗?(4)
- PHP新手上路(四)(4)
- 如何去学习PHP?(2)
- 简单入门级php分页代码(2)
- php中邮箱email 电话等格式的验证(2)