Question
Given a linked list, return the node where the cycle begins. If there is no cycle, return null
.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?
Difficulty:Medium
Category:Linked List, Two Points
Analyze
这道题目,感觉更多的是考虑数学公式的推导的样子,如果是一个环,可以得到下面这个图形:
图片来自于博客: [算法][LeetCode]Linked List Cycle & Linked List Cycle II——单链表中的环
先对图中符号做下面的定义:
X
是链表头Y
是环的第一个节点,也就是环的起点- 'Z'是快慢节点的相遇位置
- 环的长度是
r = c + b
- slow指针走过的距离是
s = a + b
- fast指针走过的距离是
2s = a + n(c+b) + b
- 相遇的时候fast指针在环里面已经走了n圈了
根据上面的图形,得到下面的推导:
- 2s = a + n(c+b) + b
- 2(a+b) = a + n(c+b) + b
- a+b = n(c+b)
- a = n(c+b) - b = (n-1)×(c+b) + c = (n-1)*r + c
所以如果在相遇的时候,重新定义一个slow2
的慢指针,每次走一步,那么他们一定可以在环的起点位置相遇的。
Solution
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
ListNode *slow2 = head;
while (slow2 != slow) {
slow2 = slow2->next;
slow = slow->next;
}
return slow2;
}
}
return nullptr;
}
};