r****o
发帖数: 1950 | 1 通常的做法是设一快一慢两个指针，fast和slow，步长分别为2和1。这样可以在O(n)的
时间内确定是否存在环。
但是如果这个fast和slow指针的步长为其他值，比如说3和1，或者4和3，是否仍然可以
确定环？如果可以的话，所用时间是否仍为O(n)? |
r****o
发帖数: 1950 | 2 我的想法是4和3的情况与2和1一样，都能在O(n)的时间内确定存在环。
但3和1的情况，能不能确定存在环呢？如果能，复杂度是多少？
欢迎各位多指点。
【在 r****o 的大作中提到】
: 通常的做法是设一快一慢两个指针，fast和slow，步长分别为2和1。这样可以在O(n)的
: 时间内确定是否存在环。
: 但是如果这个fast和slow指针的步长为其他值，比如说3和1，或者4和3，是否仍然可以
: 确定环？如果可以的话，所用时间是否仍为O(n)?
|
r****o
发帖数: 1950 | 3 2和1的情况要判断fast==slow || fast->next==slow
是不是3和1的情况判断fast==slow || fast->next==slow || fast->next->next==slow
就可以了？
是不是k和1的情况判断fast==slow || fast->next==slow || ... || fast->.....>
next==slow (共k-1个next) 就可以? 不过这个复杂度就是O(nk)了吧。
【在 r****o 的大作中提到】
: 我的想法是4和3的情况与2和1一样，都能在O(n)的时间内确定存在环。
: 但3和1的情况，能不能确定存在环呢？如果能，复杂度是多少？
: 欢迎各位多指点。
|
a**********k
发帖数: 1953 | 4 From number theory point of view, any number p(fast)
and q (slow) would work as long as GCD(p, q) = 1. |
r****o
发帖数: 1950 | 5 多谢，能解释一下吗？
【在 a**********k 的大作中提到】
: From number theory point of view, any number p(fast)
: and q (slow) would work as long as GCD(p, q) = 1.
|
d**e
发帖数: 6098 | 6 我不懂数论，但如果以纯数学计算来算，不知这样对不对
速度分别是 f 和 s, f > s
环之前的长度为 k, 环长为 m，如果经过时间 t ，两者相遇，则
(f t - k)%m = (s t - k)%m
写成 (f t - k) - m a = (s t - k) - m b
==> t = m(a - b)/(f - t)
而需要 t 取得最小，且因为一定在环里面相遇，所以 t > k
那应该是 m(a - b)/(f - t) > k
那就是说，给定 m, f, t，(a - b) > (k/m) * (f - t)
由于 t, m, (f-t)都是整数，(a-b)也是整数，而且整除(f-t)
所以 (a-b) = ceil[(k/m)] * (f-t)
所以 t = m * ceil (k/m)
1) 如果 k < m，好简单 t = m < n
2) 如果 k > m, m * c + d = n, d < m
t = m * ceil[(n - m)/m] = m * ceil[c + d/m - 1] = m * c < n
不知中途有没算错，如果这样成立，感觉
【在 r****o 的大作中提到】
: 多谢，能解释一下吗？
|
h**6
发帖数: 4160 | 7 错了，是环长len与fast-slow满足
GCD(len, fast-slow) = 1
【在 a**********k 的大作中提到】
: From number theory point of view, any number p(fast)
: and q (slow) would work as long as GCD(p, q) = 1.
|
m*****g
发帖数: 226 | 8 这个你试几个例子就知道了
如果3：1或者更大的话，快的那个可能要兜几个圈子才正好碰到慢的 |
r****o
发帖数: 1950 | 9 我现在还不是很确定，是不是3:1对各种情形的带环链表都确定能保证两个指针相遇呢?
【在 m*****g 的大作中提到】
: 这个你试几个例子就知道了
: 如果3：1或者更大的话，快的那个可能要兜几个圈子才正好碰到慢的
|
r****o
发帖数: 1950 | 10 感觉好像有道理。能不能解释一下呢?
【在 h**6 的大作中提到】
: 错了，是环长len与fast-slow满足
: GCD(len, fast-slow) = 1
|
h**6
发帖数: 4160 | 11 把步长为1的指针视为静止的参照物，步长为3的指针相当于步长为2。
如果环长为偶数，步长为2的指针可能永远也不会碰上静止的指针。 |
g**********1
发帖数: 1113 | 12 this depends on implementation. If you cmp all the all the nexts in one step
of fast with the corresponding step of the slow one. One circle is enough.
But if you only cmp the last next of the fast with the slow one, you will
miss the slow one in one circle.
【在 m*****g 的大作中提到】
: 这个你试几个例子就知道了
: 如果3：1或者更大的话，快的那个可能要兜几个圈子才正好碰到慢的
|
d**e
发帖数: 6098 | 13 这个不对吧，为什么不会碰上呢？事实上如果按你这个例子，步长1的指针会经过所有
的点，包括步长2经过的点。
举个例子，环长为6，环之前为3，两个指针分别是 1, 3，大家都由环的起点开始进入环
时间t=3时，步长1刚好进入环的起点，而步长3就已经绕了环一圈回到环的起点，碰上了
ps:谁可以看看我前面的证明对不对？
【在 h**6 的大作中提到】
: 把步长为1的指针视为静止的参照物，步长为3的指针相当于步长为2。
: 如果环长为偶数，步长为2的指针可能永远也不会碰上静止的指针。
|
r****o
发帖数: 1950 | 14 是不是说k:1的话，每次比较k次，也能保证one circle enough?
step
.
【在 g**********1 的大作中提到】
: this depends on implementation. If you cmp all the all the nexts in one step
: of fast with the corresponding step of the slow one. One circle is enough.
: But if you only cmp the last next of the fast with the slow one, you will
: miss the slow one in one circle.
|
