g*********s
发帖数: 1782 | 1 zaoxie给了个解法，是基于判定单链表是否存在循环链的解法。算法如下：
1. 维护快慢两指针。快的每次走两步，慢的走一步。一直走下去，若在某点相遇，说
明有循环链。这是经典解法。
2. 慢指针回到原表头，快指针留在相遇点，各自保持步长继续前行，再次相遇点即为
循环链起点。
注意这个带循环链的单链表形状像一个羽毛球拍。循环链相当于拍面，之前的单链相当
于拍柄。拍面
和拍柄交接处是循环链的起点。
假设拍柄长为h>=0，拍面周长c>=2。又假设第一次相遇时，慢指针走了h+x步。可证明x
去。如此快指针走了2(h+x)步，也即是(h+x)+k*c步，k>=1。那么下述等式成立：
2(h+x)=(h+x)+k*c => h+x = k*c (1)
如果慢指针回到原表头，快指针留原地，重新各自出发，保持之前步长，再次相遇时慢
指针走了h+y
步，按zaoxia说法，y==0。那么快指针走的步数是2h，也即是(c-x)+t*c。下面等式成
立：
2h=(c-x)+t*c => 2h+x = (t+1)*c (2)
由(1)和(2)得到：h = (t+1-k)*c。这显然可以构造出反例。 |
t****t
发帖数: 6806 | 2 你连人家的解法都没看清, 还质疑呢--相遇后两指针都是一步步走了, 没有快慢的分别
. 洗洗睡吧, 啊?
明x
【在 g*********s 的大作中提到】
: zaoxie给了个解法，是基于判定单链表是否存在循环链的解法。算法如下：
: 1. 维护快慢两指针。快的每次走两步，慢的走一步。一直走下去，若在某点相遇，说
: 明有循环链。这是经典解法。
: 2. 慢指针回到原表头，快指针留在相遇点，各自保持步长继续前行，再次相遇点即为
: 循环链起点。
: 注意这个带循环链的单链表形状像一个羽毛球拍。循环链相当于拍面，之前的单链相当
: 于拍柄。拍面
: 和拍柄交接处是循环链的起点。
: 假设拍柄长为h>=0，拍面周长c>=2。又假设第一次相遇时，慢指针走了h+x步。可证明x
:
|
g*********s
发帖数: 1782 | 3 更新了，呵呵。
【在 t****t 的大作中提到】
: 你连人家的解法都没看清, 还质疑呢--相遇后两指针都是一步步走了, 没有快慢的分别
: . 洗洗睡吧, 啊?
:
: 明x
|
z***e
发帖数: 5393 | 4 （我觉得我这个说法比用网球拍要通俗一些）：
这是数学题啊。
别考虑什么linked list，把图画出来先：
<--m-----> |
g*********s
发帖数: 1782 | 5 就是字符画图不方便，才用球拍类比。我觉得比喻很形象，一目了然啊。
【在 z***e 的大作中提到】
: （我觉得我这个说法比用网球拍要通俗一些）：
: 这是数学题啊。
: 别考虑什么linked list，把图画出来先：
: <--m----->
|
