《剑指Offer》-23.链表中环的入口节点

题干

如果一个链表中包含环，如何找出环的入口节点？例如，在如图所示的链表中，环的入口节点是节点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));