2-34 链表中环的入口节点

题目

• 给定一个链表，若其中包含环，则输出环的入口节点。
• 若其中不包含环，则输出null。

样例

给定如上所示的链表：
[1, 2, 3, 4, 5, 6]
2
注意，这里的2表示编号是2的节点，节点编号从0开始。所以编号是2的节点就是val等于3的节点。

则输出环的入口节点3.

思路

主要考察两知识点：

• 判断链表是否有环
• 如果有环，如何找到这个环的入口

判断链表是否有环

使用快慢指针法(Foyd判圈法)， 分别定义 fast 和 slow 指针，从头结点出发，fast 指针每次移动两个节点，slow 指针每次移动一个节点，如果 fast 和 slow 指针在途中相遇 ，说明这个链表有环。

为什么 fast 走两个节点，slow 走一个节点，有环的话，一定会在环内相遇呢，而不是永远的错开呢

首先第一点： fast 指针一定先进入环中，如果 fast 指针和 slow 指针相遇的话，一定是在环中相遇，这是毋庸置疑的。

为什么 fast 指针和 slow 指针一定会相遇呢
画一个环，然后让 fast 指针在任意一个节点开始追赶 slow 指针。
会发现最终都是这种情况， 如下图：

fast 和 slow 各自再走一步， fast 和 slow 就相遇了
这是因为 fast 是走两步，slow 是走一步

其实相对于 slow 来说，fast 是一个节点一个节点的靠近 slow 的

因此 fast 一定可以和 slow 重合。

如何找到环的入口

• 假设从头结点到环形入口节点 的节点数为x。
• 环形入口节点到 fast 指针与 slow 指针相遇节点 节点数为y。
• 从相遇节点 再到环形入口节点节点数为z。

如图所示：

相遇时：
slow 指针走过的节点数为: x + y

fast 指针走过的节点数： x + y + n(y + z)，n 为 fast 指针在环内走了 n 圈才遇到 slow 指针

因 fast 指针走过的节点数 = slow 指针走过的节点数 * 2

(x + y) * 2 = x + y + n (y + z) 简化 ⇒ x + y = n (y + z)

环形入口，表示头结点到 环形入口节点的的距离 x = n (y + z) - y。

整理公式之后为如下公式：x = (n - 1) (y + z) + z

这里 n 一定是大于等于 1 的，因为 fast 指针至少要多走一圈才能相遇 slow 指针

从头结点出发一个指针 index1，从相遇节点也出发一个指针 index2

两个指针每次只走一个节点， 当两个指针相遇的时候就是环形入口的节点

代码

class Solution
{
public:
    ListNode *detectCycle(ListNode *head)
    { // 重点在于找到快慢指针相遇点再通过相遇点找到入口
        ListNode *slow = head;
        ListNode *fast = head;
        // 当没有环的情况,fast 两步走，要预防两种越界情况
        while (fast != NULL && fast->next != NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
            // 相遇则代表有环
            if (slow == fast)
            {
                // 相同点 encounter，同时入口从链表起点开始
                ListNode *encounter = fast;
                ListNode *entry = head;
                while (entry != encounter)
                {
                    encounter = encounter->next;
                    entry = entry->next;
                }
                return entry;
            }
        }
        return NULL;
    }
};

补充

疑问就是：为什么第一次在环中相遇，slow 的 步数 是 x+y 而不是 x + 若干环的长度 + y 呢？

即文章链表：环找到了，那入口呢？中如下的地方：

首先 slow 进环的时候，fast 一定是先进环来了。

如果 slow 进环入口，fast 也在环入口，那么把这个环展开成直线，就是如下图的样子：

可以看出如果 slow 和 fast 同时在环入口开始走，一定会在环入口 3 相遇，slow 走了一圈，fast 走了两圈。

重点来了，slow 进环的时候，fast 一定是在环的任意一个位置，如图：![]

那么 fast 指针走到环入口 3 的时候，已经走了 k + n 个节点，slow 相应的应该走了 (k + n) / 2 个节点。

因为 k 是小于 n 的（图中可以看出），所以 (k + n) / 2 一定小于 n。

也就是说 slow 一定没有走到环入口 3，而 fast 已经到环入口 3 了 。

这说明什么呢？

在 slow 开始走的那一环已经和 fast 相遇了 。

那有同学又说了，为什么 fast 不能跳过去呢？ 在刚刚已经说过一次了，fast 相对于 slow 是一次移动一个节点，所以不可能跳过去 。