PHP学习之查找两个链表的第一个公共结点
Apr 25, 2019 pm 01:22 PM
php
Cari
senarai terpaut
本篇文章小编将带大家学习用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
Salin selepas log masuk
<?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; }
Salin selepas log masuk
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 } }
Salin selepas log masuk
相关教程:PHP视频教程
Atas ialah kandungan terperinci PHP学习之查找两个链表的第一个公共结点. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Artikel Panas
Repo: Cara menghidupkan semula rakan sepasukan
3 minggu yang lalu
By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
1 minggu yang lalu
By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Cara mendapatkan biji gergasi
3 minggu yang lalu
By 尊渡假赌尊渡假赌尊渡假赌
Berapa lama masa yang diperlukan untuk mengalahkan fiksyen berpecah?
3 minggu yang lalu
By DDD

Alat panas Tag

Artikel Panas
Repo: Cara menghidupkan semula rakan sepasukan
3 minggu yang lalu
By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
1 minggu yang lalu
By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Cara mendapatkan biji gergasi
3 minggu yang lalu
By 尊渡假赌尊渡假赌尊渡假赌
Berapa lama masa yang diperlukan untuk mengalahkan fiksyen berpecah?
3 minggu yang lalu
By DDD

Tag artikel panas

Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6
Alat pembangunan web visual

SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Topik panas

Panduan Pemasangan dan Naik Taraf PHP 8.4 untuk Ubuntu dan Debian

Cara Menyediakan Kod Visual Studio (Kod VS) untuk Pembangunan PHP
