总结:链表带环问题
追击问题:fast追上slow就带环
1为什么一定会相遇,有没有可能会错过?
2slow一次走1步,fast走3步,4步,5步可以吗?请证明。
假设slow进环的时候,fast跟slow的距离是N,fast追击slow距离变短。
假设slow一次走一步,fast一次走三步,假设fast和slow之间的距离是N。
相当于一次追两步,那么下一次两指针之间的距离就是N-2。
如果是奇数和偶数,会有两种不同的结果:
-1就是两个指针会错过,进入新一轮的追击,距离变成C-1(C是环的长度):
若C-1是偶数,那么追得上,若C-1是奇数,那么又再一次追不上了,陷入死循环。
总结:
1如果N是偶数,那么下一轮就追上了
2如果N是奇数,第一轮错过
C-1为偶,追上
C-1为奇,陷入死循环,永远追不上
假设slow进环时,slow和fast之间的距离是N。假设fast已经在环里面转了x圈。
slow走的距离:L
fast走的距离:L+x*C+(C-N)
fast走的距离是x的三倍,3L=L+X*C+(C-N)。
2L=(X+1)*C-N
偶数=(X+1)*偶数-奇数
这个条件不可能同时存在
永远追不上的条件是:同时存在N是奇数且C是偶数,那么永远追不上。
所以不可能永远追不上
N是偶数,C也是偶数
N是奇数,C也是奇数
结论N偶数第一轮追上
N奇数,第一轮追不上,下一轮就追上了
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;
}
相遇时slow走的路程:L+N
(慢指针有没有可能在环里走了好多圈呢,没有可能,如果走了好多圈,fast一定会超过slow
fast走的路程:L+x*C+N
2*(L+N)=L+x*C+N
L=x*C-N L=(x-1)*C+C-N