题目链接：

142. 环形链表 II

解题思路：

两个指针 fast, slow 分别从 head 开始走，slow 每次走一步，fast 每次走两步。
（情况1）如果过程中 fast 走到 None，则说明不存在环。
（情况2）否则，当 slow 和 fast 相遇后，让 slow 返回 head，fast 待在原地不动，然后两个指针每次分别走一步，当它们再次相遇时，相遇点就是环的入口。

详解：
（1）刚开始，slow 走 x 步到达环的入口 a 点；同时，fast 走了 2x 步到了环上 b 点（fast 可能已经在环上绕了几圈）；设 a → b = y, b → a = z, 则环的长度为 y + z
（2）接着，fast 走 z 步到达 a 点，再走 z 步到达 c 点；同时，slow 走了 z 步，也到达了 c 点；两指针在 c 点第一次相遇；可以得到 a → c = z, 由于环的长度为 y + z，则 c → a = y（b 和 c 关于 a 对称）
（3）由（1）可知，从 a 走 x 步可以到达 b，那么由对称性可知，从 c 走 x 步可以到达 a；所以，当 slow 和 fast 相遇后，让 slow 返回 head，fast 待在原地不动，然后两个指针每次分别走一步，当它们都走了 x 步时将会再次相遇时，相遇点就是环的入口。

（下图中，x = 2, y = 2, z = 6）

复杂度：

时间复杂度：O(n)

Python3代码：

def detectCycle(self, head: ListNode) -> ListNode:
    if not head:
        return None

    fast = head
    slow = head

    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next

        if fast == slow:
            slow = head
            while fast != slow:
                fast = fast.next
                slow = slow.next
            return fast

    return None