环形链表 II

LeetCode 142 · Medium · 1 min · 榎aaaa

如图，环外的长度为a，slow指针进入环内走了b才与fast相遇，fast走完了n圈，也就是n（b+c）+ b的距离

根据两者相遇时的时间相同，可以得到等式：a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)

当n等于1时，a=c；此时如果放置一个指针从head处向后移动，同时另一个指针从slow与fast相遇的地方以相同的速度沿着c移动，那么两者最终会在环的入口处相遇；至于为什么不考虑n，而是直接取n为1，是因为n仅仅代表着相遇处的指针多走的圈数，最后两者还是会在入口相遇

 1ListNode *detectCycle(ListNode *head)
 2    {
 3        if(head == nullptr || head->next == nullptr) return nullptr;
 4        ListNode *slow = head, *fast = head, *p1 = head;
 5        while(fast != nullptr)
 6        {
 7            slow = slow->next;
 8            if(fast->next == nullptr) return nullptr;
 9            fast = fast->next->next;
10            if(slow == fast)
11            {
12                while(p1 != slow)
13                {
14                    p1 = p1->next;
15                    slow = slow->next;
16                }
17                return p1;
18            }
19        }
20        return nullptr;
21    }