题目描述
给定一个链表,如果存在环,则返回环的入口;否则返回null
。
注意:请不要修改链表。
进一步:能否只是用额外 O(1) 的空间?
算法
(链表,快慢指针扫描) O(n)
本题的做法比较巧妙。
用两个指针 first,second 分别从起点开始走,first 每次走一步,second 每次走两步。
如果过程中 second 走到null
,则说明不存在环。否则当 first 和 second 相遇后,让 first 返回起点,second 待在原地不动,然后两个指针每次分别走一步,当相遇时,相遇点就是环的入口。
证明:如上图所示,a 是起点,b 是环的入口,c 是两个指针的第一次相遇点,ab 之间的距离是 x,bc 之间的距离是 y。
则当 first 走到 b 时,由于 second 比 first 多走一倍的路,所以 second 已经从 b 开始在环上走了 x 步,可能多余1圈,距离 b 还差 y 步(这是因为第一次相遇点在 b 之后 y 步,我们让 first 退回 b 点,则 second 会退 2y 步,也就是距离 b 点还差 y 步);所以 second 从 b 点走 x+y 步即可回到 b 点,所以 second 从 c 点开始走,走 x 步即可恰好走到 b 点,同时让 first 从头开始走,走 x 步也恰好可以走到 b 点。所以第二次相遇点就是 b 点。
另外感谢@watay147提供的另一种思路,可以用公式来说明:a,b,c,x,y 的含义同上,我们用 z 表示从 c 点顺时针走到 b 的距离。则第一次相遇时 second 所走的距离是 x+(y+z)∗n+y, n 表示圈数,同时 second 走过的距离是 first 的两倍,也就是 2(x+y),所以我们有 x+(y+z)∗n+y=2(x+y),所以 x=(n−1)×(y+z)+z。那么我们让 second 从 c 点开始走,走 x 步,会恰好走到 b 点;让 first 从 a 点开始走,走 x 步,也会走到 b 点。
时间复杂度分析:first 总共走了 2x+y 步,second 总共走了 2x+2y+x 步,所以两个指针总共走了 5x+3y 步。由于当第一次 first 走到 b 点时,second 最多追一圈即可追上 first,所以 y 小于环的长度,所以 x+y 小于等于链表总长度。所以总时间复杂度是 O(n)。
C++ 代码
/**
* 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) {
if (!head || !head->next) return 0;
ListNode *first = head, *second = head;
while (first && second)
{
first = first->next;
second = second->next;
if (second) second = second->next;
else return 0;
if (first == second)
{
first = head;
while (first != second)
{
first = first->next;
second = second->next;
}
return first;
}
}
return 0;
}
};
现在数据加强了,两层while会超时,分出来就行
这题好绕啊 我看了半小时才明白咋回事 mark一下
当s走到b时 f已经在环里面走了x距离 假设他们之后会在c点相遇 c点和环的起点距离是y(可能向图情况一样多个y距离) s和f同时回退y s回退到环起始位置 f回退到离起始距离还有y的位置 此时的f就是在环内走了x距离的位置 再加上那么再加上y就会回到起点 所以推断f点从环的起点再到环的起点 需要x+y的距离 而s和f第一次相遇的距离已经把y走了 那么f再走x的距离就会回到环的起点 把s点重制为起点 两指针同时走x 那么相遇的位置就是环的起点
来复习了
怎样证明快慢指针第一次相遇时,慢指针一定是在走它的第一圈?我是假设这时候first已经走了m圈,那最后会推出x = (n - 2m - 1)(y + z) + z,这样不影响最后结果但就是想确认,m一定为0吗
一定是第一圈相遇的,如果是第二圈,那么快指针肯定也走了两圈多,之前肯定会相遇,就矛盾了
可以考虑相对运动,此时类似于慢指针不动,快指针以速度1移向慢指针,无论此时快指针在圈内的哪个位置,移动到快指针的距离都不会超过一圈,设移动x步相遇(x<n),此时慢指针从入口走x步,也一定没有走完第一圈。
慢指针必是第一圈,快指针不超过两圈
那你还没证明快慢指针第一次相遇时,快指针一定至少走了一圈呢(doge
慢指针必定走第一圈,慢指针到达入口时,快慢指针距离假设为x,x < 圈长度,则快指针只需要走2 * x,慢指针走x步就能相遇了。
#Python格式code,同逻辑 def detectCycle(self, head: ListNode) -> ListNode: slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if (slow == fast): slow = head while (slow != fast): slow = slow.next fast = fast.next return slow
赞,可以直接拿来用了,不用翻译c++了,hh,感谢
对滴!我也希望y总的代码要是都有py版就好了、、cpp用的不是很多…大神用的语言太强了
hh, 是的!夫子绝尘,莫能及也,哈哈,还要努力啊
为什么相遇后两个指针每次分别走一步呢?
此时两个指针到环入口的距离是相等的,所以以相同速度走才会相遇。
有个不是很要紧的提醒。。。。。就是第一次相遇时 second所走的距离不一定是 x+y+z+y,这时默认second只走了一圈,但是second可以走很多圈的,所以应该是x+(y+z)*n+y。虽然这个对后面的思路没什么大的影响hhhhhhhh
说得没错!已改正hh
second只能走一圈,不能走很多圈。我们设first走了m圈,second走了n圈,第一次双方相遇时,必定存在n = m + 1。由于second总距离是first的2倍,所以成立 2 (a + b + m(c + b)) = a + b + n(c + b) => a + b = (n - 2m)(c + b) => n - 2m > 0,又因为 n = m + 1,最后推出m < 1,所以m = 0, n = 1。
第一次相遇时不一定有 n=m+1,比如在题解的图示中,当 x=100, 圈的长度是 5 时,那么当 first 第一进圈时,second就已经转了19圈了。
first,second相遇之后。问题变成了 first->next 和 起点 分别作为head的两个链表求交点(leetcode 160)
两道题目略有区别,当 first,second 相遇后,first和head 到环入口的距离是一样的,所以此时是LeetCode 160. Intersection of Two Linked Lists的特殊情况, 直接让两个指针分别从这两个点同时开始走,速度相同,相遇点就是环入口。