面试被拷打复盘 之 链表判环(快慢指针)(leetcode)
链表判环?快指针走3,4,5…行不行?为什么不行?和什么有关?什么情况下行,什么时候不行?
昨天面试被拷打了…一紧张没推出来…
答:
典中典之快慢指针?(一个走一步,一个走两步)
不是所有的步数都能判断的,需要考虑的因素很多很多…
(慢指针入环时两指针的距离D,两个指针的步数差值gap,走的次数n,环的长度len)
分析:
这里设起点s,终点t,他们相差D,即s + D = t;(t没超过环长)
则节点关系式为:s + n % len = (t + step * n) % len(1)
其中:
n:走了多少次;
Len:环的长度;
Step:快指针每次走多少步
只有满足这个关系式的时候才能相遇;
变形一下,把t拆开,s去掉:n % len = (D + step * n) % len(2)
所以,当step是2时,变形一下:(D + n) % len = 0(3)
所以我们n取klen – D就行,且一定能取到;
一般的,我们可以把(2)变形为:(D + (step - 1) n) % len = 0(4)
所以n要取:n = (k*len - D)/ (step - 1),n为整数,才能成立(快慢指针相遇)。
但是不是所有情况都能取到的,比如:step = 3,len = 4,D = 1的时候n无法为整数,所以快慢指针永远无法相遇,因此无法判断链表是否有环。
所以到这里我们知道了,快慢指针(一个一步,一个两部)一定能判断链表是否有环;
接下来我们来看一下怎么找到环的入口?
例题
我们思考一下,既然快指针比慢指针多走1步,假设从链表头到环入口长度为L,那么当慢指针到环入口时,慢指针走了L步,快指针走了2L步,而这2L步中有L步是如环前走的,有L步是如环后走的,我们不妨让L%len,那么这个L%len是不是就是快慢指针的初始差值?对吧,也就是上面的D;
由上面可知,我们n取k*len – D就有解,所以我们n不妨取len – L%len,此时也就是说我慢指针走了len – L%len步,也就是相比慢指针的初始位置s,相遇节点是s + (len – L%len),中间相差了len – L%len步,此时有没有发现,len是环的长度,那么我们是不是从相遇节点再走L步就是**(s + (len – L%len)+ L)%len**,然后把 %len全部放进去,最后剩了s节点,所以说我们从相遇节点再走L步之后就到达了s节点,也就是链表的入口处,这样我们就找到了链表的入口!
那么问题就来了,我不知道链表的入口啊,也就不知道链表头到入口的长度L,那我怎么走?
首先通过上面的分析,我们可以得到相遇节点,且从相遇节点走L到达入口,而L又是链表头到入口的长度;所以我们可以再搞一个指针指向链表头,然后两个指针(链表头指针,相遇节点指针)一起走,直到两个指针相遇,那么是不是就都走了L步,对吧。也就是找到了链表的入口处!
下面是参考代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode * f = head; //快指针
ListNode * s = head; //慢指针
ListNode * ans = nullptr;
int num = 0; //相遇次数
while(1)
{
if(f == nullptr || f->next == nullptr) break; //没有环
if(s == f) num ++; //相遇
if(num >= 2) //在环内相遇
{
ans = s;
break;
}
s = s->next;
f = f->next->next;
}
if(ans == nullptr)
{
return ans;
}
ListNode * p = head;
while(p != ans)
{
p = p->next;
ans = ans->next;
}
return ans;
}
};