问题描述:
给定一个链表,判断链表中是否有环。
首先介绍一下快慢指针:
我们定义两个指针,一快一慢。慢指针每次只移动一步,而快指针每次移动两步。
来看以下例子:
在环形链表问题中,我们用slow和fast指向链表的开始,slow一次走一步,fast一次走两步。若不带环,fast就会为空,带环,fast就会在环内追上slow
1.我们先来证明为什么slow和fast一定会在环中相遇。
- fast先进环,这时slow走了入环前距离的一半。
- 随着slow进环,fast在环内走了一段,但走了多少跟环的大小有关。
- 假设slow进环时,与fast之间的距离是n,fast开始追slow。slow每次往前走一步,fast往前走两步。所以fast和slow的距离变化:
n -> n-1 -> n-2 … 1 -> 0
每追一次,距离就减1,他们之间的距离减到0的时候就是相遇的点。
那么如何求环的入口点呢?
追上相遇的过程中:
- slow走的距离:l x
fast走的距离:l n* c x (n>=1)
(n是相遇前,fast在环内走的圈数) - 2*(l x) = l n* c x
得到:l=(n-1)* c c-x - 其中,(n-1)* c相当于从相遇点又走回到相遇点,没有变化, c-x 相当于从相遇点到相交点(顺时针)的距离。
结论: 一个指针从链表起始位置运行,一个指针从相遇点位置绕环,每次都走一步,两个指针最终会在入口点的位置相遇。
代码实现:
struct listnode *detectcycle(struct listnode *head) {
struct listnode* slow=head,*fast=head;
while(fast && fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow == fast)
{
//相遇
struct listnode* meet=slow;
while(meet != head)
{
meet=meet->next;
head=head->next;
}
return meet;
}
}
return null;
}
或者我们可以转换成链表相交的问题,即令相遇点的下一个结点为另一个链表头,这里不再细讲。
延伸问题:证明fast一次走n步时,即n>2时不一定会在环中相遇。
假设slow一次走1步,fast一次走3步,slow进环后,fast和slow之间的距离为n,fast开始追slow。
他们之间的距离变化如下:
-
n是偶数:
n -> n-2 -> n-4 … 2 -> 0
n是偶数时可以追上 -
n是奇数:
n -> n-2 -> n-4 … 1 -> -1
n是奇数时,将会错过
如果n是奇数,距离变为-1,即意味着他们之间的距离变为c-1(c是环的长度)
如果c-1也是奇数,那么就永远追不上了,
如果c-1是偶数,就可以追上。
假设slow一次走1步,fast一次走n步的推导过程与之类似。