hashmap的方法显而易见，存所有经过的节点再看以前是不是访问过即可。O(1)空间的做法需要双指针，快指针每次移动2个节点，慢指针每次移动1个节点，如果有cycle的话，两个指针最后是会相遇的。假设换的入口节点为0，最后一个节点为k - 1，长度为k。当慢指针进入环的时候:
- 如果快指针在0，那么我们找到环
- 如果快指针在x，0 < x < k，快指针和慢指针的距离小于k。由于快指针每次比慢指针多移动1的距离，所以在慢指针转完k距离回到0节点之前，快指针就可以赶上慢指针。
所以如果存在环的话，快指针一定会和慢指针相遇，假设环的长度为K，非环部分长度为L，时间复杂度O(L + K)，常数空间。代码如下:
No comments:
Post a Comment