LeetCode HOT100 - 环形链表 II

比较简单的想法就是使用哈希表，存储见过的链表节点

然后考虑空间 O(1) 的做法

比较容易想到使用快慢指针，如果它们能遇到那就说明链表存在环

但是这样我们只找到了环上的一个节点，并不保证这就是环的入口

这时候考虑从步数入手

都是从 head 出发，fast 走了 2x ， slow 走了 x，两个的差 x 就是若干个环的大小

所以 slow 和 fast 走的距离实际上都是环大小的整数倍

但是有了环的大小之后呢，如何找入口，假设入口到 head 的距离是 a ，看看能不能找一些关系

入口的形式可以表示成 a + k * x

我们要找的是 a 这个位置

如果能让 slow 或者 fast 都恰好再走 a 步就可以了

但是怎么恰好走 a 步呢，想到前面已经用过相遇的概念了，这里可以让头节点和 slow 同时开始走，当它们相遇的时候就是入口

/**
 * 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 *fa = head, *sl = head;
        while (1) {
            if (!fa || !fa->next) {
                return nullptr;
            }
            fa = fa->next->next;
            sl = sl->next;
            if (fa == sl) {
                break;
            }
        }
        fa = head;
        while (sl != fa) {
            sl = sl->next;
            fa = fa->next;
        }
        return fa;
    }
};