b0b0260fc2c94784b284d6674c964d71.png

【题目】：142. 环形链表 II

如图所示，如果有环，fast 和 slow必会相遇，此时fast走n圈，slow走一圈。由于：

  1. n = 1：a = c
  2. n > 1：a = c + (n - 1)(b + 1)
    所以可以进行两次遍历，
    第一次遍历找到相遇点；
    第二次遍历时，一个指针从相遇点开始遍历，一个指针从head处开始遍历，当这两个指针相遇时，就是到达题目所求节点。
    005b5b4182254e2cbf0e08a445433be9.png
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head, *slow = head;
        while(true) {
            if(fast == nullptr || fast->next == nullptr) {// 不相遇 - 无环
                return nullptr;
            }
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) {// 相遇 - 有环
                ListNode *a = slow, *b = head;
                while(a != b) {
                    a = a->next;
                    b = b->next;
                }
                return a;
            }
        }
        return nullptr;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

为什么slow无法走两圈？
极端情况：fast进入环时，fast = slow + 1，此时fast以相对速度1远离slow，fast需要走（环长 - 1）步才能与slow相遇，所以慢指针移动的距离 < 环长。