[PHP] 算法-请找出带环链表的环的入口结点的PHP实现
2023-02-18 15:41:45 时间
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null 1.找链表倒数第k个结点,输入一个链表,输出该链表中倒数第k个结点。第一个指针走(k-1)步,到达第k个节点,两个指针同时往后移动,当第一个结点到达末尾的时候,第二个结点所在位置就是倒数第k个节点了 2.原理有点像上面的,定义两个指针,一个是快指针每次走两步,一个是慢指针每次走一步,当两个相遇的时候,假设环的长度为n个结点,慢指针走x步,快指针走2x步,2x=x+kn ;x=kn; k暂时假定为1圈 ,也就是慢指针slow走了一个环的距离 3.快指针回到头结点,慢指针原位置不动,两个每次都是走一步,当两个再次相遇的时候,就是在环入口;想象把环捋直,和倒数第k个结点很像了 slow fast while fast!=null && fast->next!=null slow=slow->next fast=fast->next->next if slow==fast fast=head while slow!=fast slow=slow->next fast=fast->next if slow==fast return slow return null
<?php class Node{ public $data; public $next; public function __construct($data=""){ $this->data=$data; } } //构造一个带环的链表 $linkList=new Node(); $linkList->next=null; $temp=$linkList; $node1=new Node("111"); $temp->next=$node1; $temp=$node1; $node2=new Node("222"); $temp->next=$node2; $temp=$node2; $node3=new Node("333"); $temp->next=$node3; $temp=$node3; $node4=new Node("444"); $temp->next=$node4; $node4->next=$node2;//尾结点指向第二个结点 function EntryNodeOfLoop($pHead){ $slow=$pHead; $fast=$pHead; while($fast!=null && $fast->next!=null){ $slow=$slow->next;//慢指针走一步 $fast=$fast->next->next;//快指针走两步 //快慢指针环内相遇 if($slow==$fast){ //快指针回到头结点 $fast=$pHead; //同一速度再同时走 while($slow!=$fast){ $slow=$slow->next; $fast=$fast->next; } //两个相遇的点一定是环的入口 if($slow==$fast){ return $fast; } } } } var_dump($linkList); $result=EntryNodeOfLoop($linkList); var_dump($result);
object(Node)#1 (2) { ["data"]=> string(0) "" ["next"]=> object(Node)#2 (2) { ["data"]=> string(3) "111" ["next"]=> object(Node)#3 (2) { ["data"]=> string(3) "222" ["next"]=> object(Node)#4 (2) { ["data"]=> string(3) "333" ["next"]=> object(Node)#5 (2) { ["data"]=> string(3) "444" ["next"]=> *RECURSION* } } } } } object(Node)#3 (2) { ["data"]=> string(3) "222" ["next"]=> object(Node)#4 (2) { ["data"]=> string(3) "333" ["next"]=> object(Node)#5 (2) { ["data"]=> string(3) "444" ["next"]=> *RECURSION* } } }
相关文章
- redis简介
- redis底层数据结构详解
- redis分布式锁
- redis实现消息队列
- C#工具类:DotNet C# 工具类库项目
- HTML5项目笔记10:使用HTML5 IndexDB设计离线数据库
- HTML5项目笔记9:HTML5 Canvas 的图表报表开发
- HTML5项目笔记8:使用HTML5 的跨域通信机制进行数据同步
- HTML5项目笔记7:使用HTML5 WebStorage API构建与.NET对应的会话机制
- HTML5项目笔记6:使用HTML5 FileSystem API设计离线文件存储
- HTML5项目笔记5:使用HTML5 WebDataBase设计离线数据库
- HTML5项目笔记4:使用Audio API设计绚丽的HTML5音乐播放器
- HTML5项目笔记2:离线系统表单设计
- HTML5项目笔记1:项目准备和工具使用
- Web前端设计模式--购物车拖拽的实现...
- LinQ构建分层架构
- Web前端设计模式--构建Ajax智能搜索...
- Web前端设计模式--制作漂亮的弹出层...
- Web 前端设计模式--Dom重构...
- Web前端设计模式--jQuery验证插件...