142 环形链表II
思路
- 判断链表是否有环
- 本题还需要找环的入口,通过推理我们得到:相遇后,设定一个指针在head起始位置,另一个在相遇位置,两个指针同时走相同步数一定能在环入口相遇
推导过程:
- 假设head到环的起点距离为a,环的长度为len
- 第一次到环的起点,毫无疑问只有fast(fast走的距离是slow两倍,slow追不上fast)
- 第二次到环的起点,slow一定到达。fast不一定到达
- 如果len恰好等于a,由于fast走的距离是slow两倍,fast走2a = a + len,fast恰好到达环的起点与slow相遇,那么slow和fast在环的起点相遇,得到问题的解
- 否则,无论len < a或者len > a,fast一定不在环的起点,并且与环的起点/slow相距k(k一定小于len)
- 我们讨论len != a的情况,由于slow和fast相距k(k < len),两者需要多久相遇呢,给出结论:一圈内。这是因为k < len,fast每次都比slow多走一步,所以fast追上slow需要走k步,而k < len。
- 我们已经知道slow和fast下次相遇在一圈内(这解释了为什么slow一定走a + m)。请注意:此时只是第二次到达环的起点,还没到第三次。这意味着slow还没走环 假设两者相遇,此时slow走了a + m步, fast走了2(a + m)步,有等式2(a + m) == a + m + n * len(n为fast走过的环的圈数),化简得到a == (n - 1) * len + len - m
- len - m实际上是fast到环的起点的距离,因此我们可以知道,让slow从head开始,fast仍然在原来的位置,fast和slow同时移动,slow到达环的起点走的a步 == fast到达环的起点走的len - m步,两者相遇在环的起点
综上所述:
- 无论环的长度len与head到环的起点a的大小关系如何,两者第一次相遇之后令slow = head,第二次两者一定相遇在环的起点
- slow进入环的起点后,slow和fast一定在一圈内相遇,所以slow走的步数一定为a + m,而不是a + m + u * len(u为slow经过环的次数)
Solution
/**
* 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* fast = head, * slow = head;
while(fast != nullptr && fast->next != nullptr){
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
break;
}
// 没有环的情况:
// 1. 没有元素,fast == nullptr
// 2. 只有一个元素,fast->next == nullptr
// 3. 递归思想,假设遍历了若干元素并且没有环,剩余元素一定为情况1或情况2
if(fast == nullptr || fast->next == nullptr){
return nullptr;
}
// 否则有环,此时fast == slow两指针在环内相遇
// 假设slow走了k,那么fast走了2k,比slow多走了k,k刚好是圈长度的整数倍(k = n * size)
// 假设环入口离相遇点为m,那么slow从头走到环入口需要k - m,而fast走到环入口路程也为k - m
// 因此让slow从head开始走,fast和slow走相同距离
slow = head;
while(fast != slow){
fast = fast->next;
slow = slow->next;
}
return slow;
}
};