doclist 阅读(5) 评论(0)

龟兔赛跑算法(Floyd's Tortoise and Hare/Circle Detection)用于判断链表是否有环.

使用两个指针,一个慢的每次走一步,一个快的每次走两步.

可以在O(n)的时间复杂度和O(1)的空间复杂度解决如下三个问题:

 

1. 判断链表是否有环?

两个指针相遇了,肯定有环.(例题)

为什么有环就会相遇呢?

证明:

令:  head=头节点;  entry:环的入口处节点;  meeting:相遇时所在的节点.

   C=环的长度;  L1=head到entry的距离;  L2=entry到meeting的距离.

   慢的每次走一步(速度为1),快的每次走两步(速度为2).同时出发,相遇时有:

   L1+L2+n1*C = (L1+L2+n2*C)/2    化简得:

   L1 = (n2-2*n1)*C-L2  

   其中L1 和C是定值,这个等式显然有解,所以会相遇.

 

2. 环的长度?

相遇后,一个不动,另一个一步一步走一圈,再次相遇时,走过的路程就是环的长度.

 

3. 环的入口?(例题)

根据L1 = (n2-2*n1)*C-L2  

L1实际上等于先转几圈加上最后一圈减去L2

所以再让一个节点从head出发,一个节点从meeting出发,同时走,每人每次一步,最后相遇肯定在entry节点,也就找到了entry节点. 

 图示: