PHP实现找出链表中环的入口节点

1. 题目描述

这道题目给出一条链表，其中部分节点组成一个环，请找出环的入口节点。链表节点的定义如下：

class ListNode {
    public $val;
    public $next = null;
    function __construct($val){
        $this->val = $val;
    }
}

其中，链表的头节点为 `head`。

2. 解题思路

这道题可以使用快慢指针的解法。快慢指针的基本思路是，使用两个指针在链表上同时遍历，其中一个指针的速度比另一个指针快。如果链表存在环，那么两个指针总有一刻会相遇。

设链表头节点到环入口节点的距离为 $a$，环入口节点到两指针相遇点的距离为 $b$，两指针相遇点到环入口节点的距离为 $c$。则有以下关系：

设慢指针走过的路程为 $x$，则快指针走过的路程为 $2x$

在相遇点，快指针比慢指针多走了 $n$ 个环的距离，即 $2x = x + nb + nc$

又有 $2x = x + 2nb + 2nc$，其中 $2nb$ 表示快指针走过的距离，$2nc$ 表示快指针从相遇点再绕过一圈环后的距离

根据式子 (2) 和式子 (3)，可以得出 $x = nb - nc$。意思是，慢指针走过了环的整数倍距离。此时，如果让慢指针重新从头节点出发，并且让快指针也每次只走一个节点，那么它们会在环的入口节点相遇。

3. 代码实现

根据上面的思路，我们可以得到以下解法：

class Solution {
    function detectCycle($head) {
        $fast = $slow = $head;
        while ($fast != null && $fast->next != null) {
            $fast = $fast->next->next;
            $slow = $slow->next;
            if ($fast == $slow) {
                $p = $head;
                while ($p != $slow) {
                    $p = $p->next;
                    $slow = $slow->next;
                }
                return $p;
            }
        }
        return null;
    }
}

其中，$fast$ 表示快指针，$slow$ 表示慢指针，$head$ 是链表头指针。在快慢指针相遇后，设置一个指针 $p$，让它从头节点开始遍历，直到与慢指针相遇。这个相遇点就是环的入口节点。

4. 总结

这道题目使用快慢指针的方法比较巧妙。通过两个指针在链表上的遍历，可以找出环的入口节点。这个方法还可以用于其他问题，例如判断链表是否存在环，找出链表中间节点等。