- 一快一慢双指针，快指针每次移动2的距离，慢指针移动1，存在环的话最终会相遇，这一点在前一道题中已经证明过。假设相遇的点为x
- 快指针重新移到head，慢指针仍然指向x，快慢指针此时每次只移动1的距离，两个指针一定相交于换的入口处
为了证明第二点，我们需要定义几个参数。假设环的入口节点为0，长度为K，最后一个节点为K - 1。假设从head到0节点的长度为L。在前一道题中我们已经证明过，不管环有多大，慢指针在跑完一圈之前就会被快指针赶上，假设慢指针跑过的路程为m，快慢指针第一次相遇的节点距离0节点为x，在相遇之前，快指针可能已经跑了n圈，下列方程一定成立：
- 2 * m = 2 * (L + x) = L + x + n * K
右边是快指针跑过的距离，左边是慢指针跑过的距离乘以2，两者肯定相等。进一步我们可以得到：
- L = n * K - x
两边对K取余，我们有:
- L % K = (K - x) % K
上面这条等式代表的正是x和圆环的入口0节点的距离对K取余后就等于节点0和head的距离L对K取余。也就是说，不管L有多大，K有多小，慢指针从x开始继续移动不管转了多少圈，最后一定会和快指针在0节点相遇。第二点得证。时间复杂度O(N)，常数空间，代码如下:
No comments:
Post a Comment