龟兔赛跑 / Floyd判圈算法概述
(对应力扣142. 环形链表 II,141. 环形链表 I)
判断一个链表是否存在环
龟兔赛跑 / Floyd判圈算法 转换成判断链表是否存在 “环” 问题可以总结以下三点:
- 定义两个指针（慢指针和快指针），初始时都指向链表的头节点。
- 两个指针以不同速度移动(一个快一个慢).
- 如果链表中存在环，快指针和慢指针最终会相遇（指向同一个节点），否则快指针会到达链表的末尾（指向NULL）。
满足这三个条件之后,只要链表存在"环",那么速度快的指针和速度慢的指针一定会相遇(指向同一处节点即为相遇),并且被两个指针所指向的这个节点一定是在链表中的"环"的起点以及"环"的起点之后中的位置!
注释 :可能有人会疑问：快指针有可能会跳过慢指针，以致两个指针不会相遇(指向同一个节点)。这种情况确实存在.
但在实际操作中（判断链表是否存在环），我们通常定义快指针每次移动两个节点，慢指针每次移动一个节点。这样，即使快指针会跳过某些节点，慢指针会遍历到所有节点，最终快指针和慢指针一定会在某处相遇。
画图演示两个指针相遇的情况:
- 速度快的指针为蓝色三角形
- 速度慢的指针为紫色三角形
//p 为慢指针, q 为快指针
while(q != NULL && q->next!=NULL){
p = p->next;
q = q->next->next;
if(p == q) {
//后续操作处理.....
}
}
-
开始两个指针都指向头节点(head)
-
后面每一次循环,快指针移动两个距离,慢指针移动一个距离
-
循环继续
-
到这里两个指针指向的节点相同,就可以做后续的处理了
查找链表中环的首个节点
我们可以通过上面的方法判断链表中是否存在环
那么如何找到环的首个节点?
我们继续使用上面的例子
我们定义:
- head到环的起始节点的距离为a，环的起始节点到相遇节点的距离为b，相遇节点到环的起始节点的距离为c。
- 当快慢指针相遇时，快指针已经绕环n圈。
(因为这里是单链表,只有next指针,不能从后向前访问,所以只能用指向后一项的指针)
注意这里的while循环,快指针是慢指针速度的两倍,也就是相同的时间内(同一个循环中)快指针移动的距离是慢指针移动的距离的两倍
数学公式表示为:
(n 为链表中快指指针从环的起始点绕一圈的次数)
慢指针的距离为: a+b
快指针的距离为: 2(a+b)
根据上面的对距离的定义还可以得出:
q= (a+b) + (b+c)*n
即得出方程
2(a+b) = (a+b) + (b+c)*n
2a+2b = a+b+nb+nc
a = - b+nb+nc
a = - b+nb+nc+c - c
a = (n-1)b + (n-1)c +c
a = (n-1)(b+c) + c
- 此时如果n为1(当n=1时，表示快指针绕环一次),可以得出结论 a = c 即:
头节点 到 环的起始节点的距离 = 两个指针相遇的节点 到 环的起始点的距离.
换言之，头节点到链表中环的起始节点的距离等于两个指针相遇的节点到环的起始节点的距离。因此，无论在环中循环多少次，这两个距离始终相同。