142. 环形链表 II

142. 环形链表 II - 力扣（LeetCode）

class Solution {
public:
  ListNode *detectCycle(ListNode *head) {
    ListNode *Slow = head;
    ListNode *Fast = head;
    while (Fast && Fast->next) {
      Slow = Slow->next;
      Fast = Fast->next->next;

      if (Slow == Fast) {
        ListNode *Head = head;
        while (Head != Slow) {
          Head = Head->next;
          Slow = Slow->next;
        }
        return Head;
      }
    }
    return nullptr;
  }
};

能想到快慢指针很好，但是这个时候真的需要用数学来解决一下问题了。

$$ a=c+(n−1)(b+c) $$

两边对环的周长 $b+c$ 取模，事实上就可以得到

$$ a \equiv c\ \mathrm{mod} (b+c) $$

也就是说，在两个指针第一次相遇之后，我们就可以让 Slow 继续走完余下路程的同时，新指针Head 也走 $c$ 步，由于 $c$ 与 $a$ 同余，并且此处是 Slow 指针而不是 Fast 指针在走——此处为重点，这意味着 $(n-1)(b+c)$ 这一项可以直接被消去——所以我们就可以得到第一个入环的结点了。

二刷

我的妈啊，这个思路是有的，但是细节上面的处理一定要注意。下面这种写法是不行的。

class Solution {
public:
  ListNode *detectCycle(ListNode *head) {
    ListNode *Slow = head;
    ListNode *Fast = head;
    while (true) {
      if (!Fast || !Fast->next)
        return {};
      // XXX
      if (Fast == Slow) {
        ListNode *Finder = head;
      }
      Slow = Slow->next;
      Fast = Fast->next->next;
    }
    while (Finder != Slow) {
      Slow = Slow->next;
      Finder = Finder->next;
    }
    return Finder;
  }
};

看着很整齐，是不是？但其实你别忘了你的 Slow 和 Fast 一开始就都被赋值成 head 了，所以那句 Fast == Slow 是永远为真的。有点搞。

所以这道题的正确方法应该是：先让 Slow 和 Fast 往前走，然后再考虑两个等于不等于的问题。但是由于我们要考虑 Fast 指针的可用性，就需要多写一些 guards 了。

class Solution {
public:
  ListNode *detectCycle(ListNode *head) {
    ListNode *Slow = head;
    ListNode *Fast = head;
    while (Fast) {
      // At the beginning, if Fast != nullptr, Slow must be so too.
      Slow = Slow->next;
      // However, we still need to validate Fast->next. This won't make our
      // `Fast += 2; Slow += 1;` strategy fail, since if Fast->next is not
      // available here, it means that we don't have cycles in this list.
      if (!Fast->next)
        return {};
      Fast = Fast->next;
      // In order to discriminate between exit when Fast->next unavailable and
      // exit when Fast == Slow, we can only embed the another while loop here.
      if (Fast == Slow) {
        ListNode *Finder = head;
        while (Finder != Slow) {
          Slow = Slow->next;
          Finder = Finder->next;
        }
        return Finder;
      }
    }
    return {};
  }
};

从这里你可以看出来，这个题目或许真的只能这么写……各种乱七八糟的 guards 和套叠，但只有这么写，这种方法才能奏效。只能说的确有那么点黑魔法的意思在里面。

虽然但是，其实哈希集合也未必不好用……

class Solution {
public:
  ListNode *detectCycle(ListNode *head) {
    unordered_set<ListNode *> Visited;
    while (head) {
      if (!Visited.contains(head))
        Visited.insert(head);
      else
        return head;
      head = head->next;
    }
    return {};
  }
};

三刷

class Solution {
public:
  ListNode *detectCycle(ListNode *head) {
    ListNode *Fast = head, *Slow = head;
    while (Fast && Fast->next) {
      Slow = Slow->next;
      Fast = Fast->next->next;
      if (Fast == Slow)
        break;
    }
    if (!Fast || !Fast->next)
      return nullptr;

    Slow = head;
    while (Fast) {
      if (Fast == Slow)
        break;
      Fast = Fast->next;
      Slow = Slow->next;
    }
    return Slow;
  }
};

其实这个到底是不是比二刷的方法更好理解一点我也不太清楚，不过倒是确实更适合死记硬背了。