题干
如果一个链表中包含环,如何找出环的入口节点?例如,在如图所示的链表中,环的入口节点是节点3。
graph LR
1-->2
2-->3
3-->4
4-->5
5-->6
6-->3
解题思路
第一步需要先确定链表中是否存在环
使用两个指针,一个步长为1,另一个步长为2,两个指针同时移动,当第二个指针追上第一个指针时,说明链表中有环,否则无环。
第二步确定环中节点数
当第一个指针和第二个指针相遇时,肯定是在环中,所以可以从相遇的位置开始计数,直到再回到当前位置为止,得到环中节点个数n。
第三步找到环的入口节点
再将两个指针置回头节点位置,然后第一个指针先走n步,然后两个指针同时开始,当两个指针相遇时所在节点就是入口节点。
❓疑问❓
是否可以考虑使用辅助空间记录下每个访问过的节点的标识信息,当出现的第一个重复访问就是入口节点,否则就是没有环的链表。
代码实现
<?php
class ListNode
{
private $val;
private $next;
public function __set($name, $value)
{
$this->$name = $value;
}
public function __get($name)
{
return $this->$name;
}
}
$node1 = new ListNode();
$node1->val = 1;
$node2 = new ListNode();
$node2->val = 2;
$node1->next = $node2;
$node3 = new ListNode();
$node3->val = 3;
$node2->next = $node3;
$node4 = new ListNode();
$node4->val = 4;
$node3->next = $node4;
$node5 = new ListNode();
$node5->val = 5;
$node4->next = $node5;
$node5->next = $node3;
function meetingNode($head)
{
if (empty($head)) {
return null;
}
$slow = $head->next;
if (empty($slow)) {
return null;
}
$fast = $slow->next;
while (!empty($fast) && !empty($slow)) {
if ($fast == $slow) {
return $fast;
}
$slow = $slow->next;
$fast = $fast->next;
if (!empty($fast)) {
$fast = $fast->next;
}
}
return null;
}
function findEntryNode($head)
{
$meetingNode = meetingNode($head);
if (empty($meetingNode)) {
return null;
}
// 计算环中节点数
$nodesInLoop = 1;
$node = $meetingNode;
while ($node->next != $meetingNode) {
$node = $node->next;
++$nodesInLoop;
}
$node = $head;
for ($i = 0; $i < $nodesInLoop; $i++) {
$node = $node->next;
}
$node2 = $head;
while ($node != $node2) {
$node = $node->next;
$node2 = $node2->next;
}
return $node;
}
var_dump(findEntryNode($node1));