题解 | #链表中环的入口结点#

<?php
/*class ListNode{
    var $val;
    var $next = NULL;
    function __construct($x){
        $this->val = $x;
    }
}*/
function EntryNodeOfLoop($pHead)
{
    if($pHead == null || $pHead->next == null){
        return null;
    }
    $fast = $pHead;
    $slow = $pHead;
    while($fast != null){
        $slow = $slow->next;
        $fast = $fast->next;
        $fast = $fast->next;
        if($slow == $fast){
            // 此时两个指针在环的中间节点, 定理：碰撞点p到入口结点的距离 = 头结点到入口节点的距离
            $p2 = $pHead;
            while($slow != $p2){
                $slow = $slow->next;
                $p2 = $p2->next;
            }
            return $p2;
        }
    }
    // 不包含环，返回null
    return null;
}

有定理: 碰撞点p到连接点的距离=头节点到连接点的距离,因此分别从碰撞点,头节点相同速度开始走相遇的那个点就是连接点.

定理证明如下(from csdn):

设头节点到连接点的距离为x,连接点到碰撞点的距离为y,碰撞点到连接点的距离为z,环的长度为n,
(1) 碰撞点到头节点的距离为n,则有x+y=n
(2) 又因为环的长度为n,则有y+z=n
(3) 由(1),(2) 可得,碰撞点p到连接点的距离=头节点到连接点的距离