题目描述

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

若其中不包含环，则输出null。

样例

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

则输出环的入口节点3.

算法

(链表，快慢指针扫描) $O(n)$

1. 快慢指针扫描整个链表，慢指针 first 走一步，快指针 second 走两步
2. 在走的过程中如果快指针为空，说明链表中无环，否则直到两个指针第一次相遇为止，假设在 c 点相遇
3. 此时，慢指针从头开始走，快指针从点 c 开始走每次走一步，再次相遇的点就是链表环的入口

图示：

上面做法为什么是对的？
假设链表存在环，快慢指针从点 a 开始走，b 是链表的入口节点，c 是快慢指针在环中第一次相遇点，其中 ab 之间的距离是 x，bc 之间的距离是 y
那么当慢指针后退 y 步即当 first 走到 b 点时，快指针应该从 c 点后退 2y 步，此时慢指针走了 x 步，快指针应该走了 2x 步，那么在环里就走了 x 步，再走 y 步就到了 b 点，因此我们可以知道从点 b 走 x + y 步就可以回到 b 点。

根据这个性质，让慢指针从 a 点开始走 x 步，让快指针（此时每次走一步，也是慢指针）从 c 点走 x 步必然会在 b 点相遇。

时间复杂度

操作 1 和 2 快慢指针走了 3(x + y) 步，操作 3 快慢指针走了 2x 步，总共走了 5x + 3y，而链表的长度为 2x + y 步，所以时间复杂度是线性的，$O(n)$

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if (!head || !head->next) return nullptr;

        auto first = head, second = head;
        while (first && second)
        {
            first = first->next;
            second = second->next;
            if (second->next) second = second->next;
            else return 0;

            if (first == second)
            {
                first = head;
                while (first != second)
                {
                    first = first->next;
                    second = second->next;
                }
                return first;
            }
        }

        return 0;
    }
};