判断是否存在环

定义两个指针 p1,p2,从head节点开始遍历,每次循环p1向前移一位,p2向前移两位,若链表存在环则p1,p2必然有相等的时候。

function hasCycle($linkedList)
{
 	$p1 = $p2 = $linkedList->headNode;
 	while ($p1->nextNode) {
        $p1 = $p1->nextNode;
        $p2 = $p2->nextNode->nextNode;
        if ($p1 == $p2) {
            return true;
        }
 	}

 	return false;
}

找出环的位置

假设 p1 经过的路程是 S,因为 p2 速度是 p1 的 2 倍,所以 p2 经过的路程为2S

假设 p2 比 p1 多走n圈的距离才到达汇合点,那么可以得出:

$2S = S + NR$ 即$S=NR$

代入 $2S = A+ X + NR$

得出 $NR = A + X$

又 $R=X+T$

代入得

$NR=A+R-T$$ 即 $$A=(N-1)R+T$

根据上述推导的公式可以得出结论:从汇合点和起点的两个指针定会在环的交点相遇!

代码来了

function getCycleNode($linkedList)
{
 	$p1 = $p2 = $linkedList->headNode;
 	while($p1->nextNode) {
        $p1 = $p1->nextNode;
        $p2 = $p2->nextNode->nextNode;
        if ($p1 == $p2) {
            break;
        }
 	}
    
    if (!$p1) {
        return false;
    }
    $p3 = $linkedList->headNode;
    while($p1 != $p3) {
        $p1 = $p1->nextNode;
        $p3 = $p3->nextNode;
    }
    
    return p1;
}