结论
快指针一次走2步,慢指针一次走1步。当两指针第一次相遇时,让慢指针回起点,然后快慢指针同时一次走1步,最后相遇的点就是入口结点。
解释
首先易得快慢指针相遇一定在环内。
假设环入口距起点x,相遇的地方在环入口后方y步。
如果让慢指针退y步,即在环入口,此时快指针退了2y步,也就是差y步走到环入口。这时慢指针从头走了x步,快指针走了2x步,其中x步在环内走的,易得:x+y为环的整数倍。
在两指针第一次相遇后,让慢指针回到头结点,然后快慢指针同时一次走1步,当慢指针走了x步时,到达环入口;快指针也走了x步,加上之前距离入口结点的那y步,也到达了环入口。