判断是否存在环

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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$

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

代码来了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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;
}