关于Floyd判圈算法

发布时间:2016-12-9 17:53:52 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"关于Floyd判圈算法",主要涉及到关于Floyd判圈算法方面的内容,对于关于Floyd判圈算法感兴趣的同学可以参考一下。

问题:给你一个链表,要求判断链表里是否有环,若有,求出环长. Floyd算法:两个指针p1,p2.最开始先全都指向链表头,p2移动的速度比p1快一倍,若该链表无环,则p2指向空指针时,就代表没有即得证无环。若当p2走了链表某一点两次时,即代表有环. 假设链表头距离环的距离是x(此即环的起点,两节点相邻表示其彼此相距1个单位,若中间有个节点则彼此相距2个单位,这里距链表头x单位处的节点是属于环的,但是p1和p2移动时不一定会经过这个点),环的长度为n; 则当p1和p2第一次相遇时,假设p1走了i个单位,则i = x + a*n + k; 又p2比p1快一倍,所以p2走了2i,则2i = x + b*n + k; k为距离环的起点的距离。 相减得到i = (b-a)*n; 因此i为环长的倍数。 为了求出环长,可在相遇之后,让两者一起再继续移动,当再次相遇时,p2比p1多出来的步数单位就是环长(这里是假设了p2快了p1一倍,若是两倍则另当别处,不过道理相同)。 参考资料: http://blog.csdn.net/thestoryofsnow/article/details/6822576 http://03071344.lofter.com/post/10871e_29fdd8 http://blog.csdn.net/qq415200973/article/details/11494471

上一篇:尾递归与Continuation(转)
下一篇:重写require使lua文件模块化

相关文章

相关评论