知道用步长法判断单链表是否有环 ，但一直不知道为什么可以这样，下班无事，尝试证明一下：
假设带环单链表Ｌ如下：
1(h) -> 2 -> 3 -> 4(s) -> 5 -> 6 -> 7 -> 8 -> ... -> m ->... -> n-2 -> n-1 -> n(e)- >4
证明：
单链表可分为两种，要么有循环，要么循环：）无循环的单链表，使用步长法时快指针因为比慢指针每次多走一步，所以它总是先走到终点退出，不可能相遇。所以单链表使用步长法如果相遇了，则肯定表明链表有循环。
下面来证明对于循环单链表，步长法是可能相遇的
令x=dist(h, s)，表示链表头h到循环起点s的距离, 可知x>=0
y=dist(s,e)，表示链表循环部分的长度, 可知y>=1
z=dist(s,m)，表示起点s到相遇点m的距离,可知1<=z<=y
z表示使用步长法时，快慢指针ps, pf相遇的位置．z必定位于s和e之间．
如果步长法是正确的，ps, pf相遇于m, 现在需证明m是存在的。
此时必有：
ps走的距离：(x + z) + ky (k>=0)
pf走的距离：2(x+z) + 2ky
因为ps,pf相遇，所以有：
2(x+z)+2ky - ((x+z)+ky) = my (m>=1)
即需证明存在这样的z, m, k ,满足: x+z = (m-k)y (m-k >=1)
z = (m-k)y - x , (x>=0, y>=1, 1<=z<=y)
可见，有多组m, k，使得上式满足，我们可以得到这样的z.
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
