环形链表 II

给定一个链表的头节点 head，返回链表开始入环的第一个节点。

如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置，索引从 0 开始。

如果 pos 是 -1，则在该链表中没有环。

注意：

• pos 不作为参数进行传递。
• pos 仅仅是为了标识链表的实际情况。
• 不允许修改链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

• 链表中节点的数目范围在 [0, 10^4] 内
• -10^5 <= Node.val <= 10^5
• pos 的值为 -1 或者链表中的一个有效索引

进阶：

你是否可以使用 O(1) 空间解决此题？

解法一（哈希集合）：

/**
 * 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) {
        unordered_set<ListNode*> visited;

        ListNode* cur = head;
        while (cur != nullptr)
        {
            if (visited.count(cur))
            {
                return cur;
            }

            visited.insert(cur);
            cur = cur->next;
        }

        return nullptr;
    }
};

解法二（快慢指针）：

/**
 * 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* slow = head;
        ListNode* fast = head;

        while (fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast)
            {
                ListNode* p1 = head;
                ListNode* p2 = slow;

                while (p1 != p2)
                {
                    p1 = p1->next;
                    p2 = p2->next;
                }

                return p1;
            }
        }

        return nullptr;
    }
};

核心思想

这题和“环形链表”很像，区别在于：

• 那道题只需要判断有没有环
• 这道题需要找到环的入口节点

如果链表有环，先用快慢指针判断是否存在相遇。

一旦快慢指针相遇，就说明链表中一定有环。

接下来要找环的入口。

这题最关键的观察是：

当快慢指针第一次相遇后，再用一个指针从头节点出发，另一个指针从相遇点出发，它们每次都走一步，最终会在环入口相遇。

解法一：哈希集合

遍历链表时，把每个访问过的节点地址存入哈希集合。

如果当前节点已经出现过，说明从这个节点开始再次走到了同一个节点。

由于我们是按顺序遍历的，第一次重复出现的节点就是环的入口。

所以直接返回当前节点即可。

这个方法很直接，但需要额外空间。

解法二：快慢指针 + 数学推导

1. 先判断链表是否有环

使用快慢指针：

• slow 每次走一步
• fast 每次走两步

如果链表无环，fast 会先走到末尾，返回 nullptr。

如果链表有环，slow 和 fast 一定会在环中相遇。

2. 相遇后如何找到入口

设：

• 从头节点到环入口的距离为 a
• 从环入口到相遇点的距离为 b
• 从相遇点回到环入口的距离为 c

那么整个环长为：

b + c

快指针走的路程是慢指针的两倍。

设慢指针走了 a + b 步到达相遇点，那么快指针走了：

2(a + b)

快指针比慢指针多走的部分，一定是若干圈环长度：

2(a + b) - (a + b) = a + b = k(b + c)

整理得：

a = k(b + c) - b

也就是说，从头节点走 a 步到达入口，等价于从相遇点再走 a 步。

而由于：

a = (k - 1)(b + c) + c

所以相遇点再走 c 步就能回到入口。

因此：

• 一个指针从 head 出发
• 另一个指针从相遇点出发
• 两者每次都走一步

最终一定会在环入口相遇。

为什么从头节点和相遇点同时走一步会相遇在入口

第一次相遇时，慢指针在环中走了 b 步。

从头节点到入口是 a 步。

根据路程关系可得，头节点到入口的距离 a，正好等于相遇点到入口沿着环走的距离，再加上若干整圈。

所以一个指针从头节点出发，另一个从相遇点出发，它们都以相同速度前进时：

• 从头节点出发的指针，先走到入口
• 从相遇点出发的指针，也会在走完相同步数后回到入口

因此它们会在入口位置重合。

边界情况

如果链表为空：

head == nullptr

没有节点，自然没有环，返回 nullptr。

如果链表只有一个节点：

• pos = -1 时，没有环，返回 nullptr
• pos = 0 时，节点自己指向自己，入口就是这个节点

快慢指针算法都能正确处理。

正确性证明

我们证明：快慢指针算法返回的节点一定是环入口。

结论 1：如果链表无环，算法返回 nullptr

无环链表从头节点沿 next 指针一直向后，最终一定会到达 nullptr。

快指针每次走两步，因此会更早到达链表末尾。

当：

fast == nullptr || fast->next == nullptr

时，循环结束，算法返回 nullptr。

所以无环时结果正确。

结论 2：如果链表有环，快慢指针一定会相遇

快指针每轮比慢指针多走一步。

进入环后，两者都在环中移动，环上的相对距离每轮变化 1。

环长有限，因此它们一定会在某一时刻重合，即：

slow == fast

所以有环时一定能检测到相遇。

结论 3：相遇后，一个指针从头节点出发，另一个指针从相遇点出发，同速前进会在入口相遇

设头节点到入口的距离为 a，入口到相遇点的距离为 b，相遇点回到入口的距离为 c。

根据快慢指针的速度关系，可以得到：

a = k(b + c) - b

也就是说，从头节点走 a 步到入口，和从相遇点走若干步回到入口是同步对应的。

因此两个指针每次都走一步，最终会在入口相遇。

结论 4：第一次相遇点不是入口，但能推出入口

第一次相遇发生在环内部，不一定就是入口。

但相遇点包含了足够的环信息，可以和头节点一起用来定位入口。

所以算法不会把相遇点误当成入口，而是会继续移动两个指针直到真正的入口。

得出结论

由结论 1 可知，无环时返回 nullptr 正确。

由结论 2 可知，有环时一定能检测到相遇。

由结论 3 和结论 4 可知，相遇后再同步前进一定会找到环入口。

因此算法正确。

举例理解

以：

head = [3,2,0,-4], pos = 1

为例，链表结构是：

3 -> 2 -> 0 -> -4
     ^         |
     |_________|

快慢指针第一次相遇后，说明链表中有环。

此时再让一个指针从头节点 3 出发，另一个从相遇点出发。

它们每次都走一步，最终都会来到值为 2 的节点，也就是环入口。

所以返回这个节点。

复杂度分析

解法一

遍历链表一次，哈希集合最多存储所有节点。

• 时间复杂度：O(n)
• 空间复杂度：O(n)

解法二

快慢指针判断环和寻找入口都只需要线性时间。

只使用了常数个指针变量。

• 时间复杂度：O(n)
• 空间复杂度：O(1)

解法二满足进阶要求，是更推荐的做法。