142. 环形链表 II

题目链接：142. 环形链表 II

题目描述

给定一个单向链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

核心思考：快慢指针与数学推导

这道题是经典的“验证环形链表并寻找入口”问题，主要考察了**双指针（快慢指针）**技巧以及背后的数学原理。求解过程分为明确的两步：

1. 判断是否有环

定义两个指针：快指针 p1 每次向前走两步，慢指针 p2 每次向前走一步。如果链表存在环，这两个指针必定会在环内的某个节点相遇。如果在遍历过程中 p1 或者 p1.next 变为空，说明提前走到了链表尽头，可以直接判定为无环。

2. 定位环的入口位置

这是一道典型带有推导过程的数学题。假设链表头节点到环入口的距离为 $L$，环入口到快慢指针相遇点的距离为 $k$，环的总周长为 $C$。
当快慢指针相遇时：

• 慢指针 p2 走过的路程为：$L + k$
• 快指针 p1 走过的路程为：$L + n \times C + k$（$n$ 为快指针已经绕环的圈数）

因为快指针的速度恒为慢指针的两倍，路程差也可得出如下等式：$2(L + k) = L + n \times C + k$
我们将等式稍微化简一下：$L = (n - 1) \times C + (C - k)$

这句话的直观含义是什么？
等式的左边 $L$ 是从头节点走到环入口的距离；等式的右边指出，如果我们将指针从相遇点继续顺时针往下走 $C-k$ 的距离（也就是走到环入口），再额外走完几整圈，总距离刚好等于 $L$。

因此，破局的方法就是：把其中一个指针重新移回链表头部 head，另一个指针依然停在相遇点。随后让两个指针同时每次只走一步。当头部的新指针走完 $L$ 距离到达入口时，环内的指针也必然刚好“转完圈子”走到了入口处。两者相遇的地方，就是环入口。

解题思路 (Python)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        p1 = head
        p2 = head
        while p1 != None and p1.next != None:
            p1 = p1.next.next
            p2 = p2.next
            if p1 == p2: 
                break
        if p1 == None or p1.next == None:
            return None
        p1 = head
        while p1 != p2:
            p1 = p1.next
            p2 = p2.next
        return p2

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是链表节点的总数。在第一阶段判断是否有环时，两指针绕行最多不会超过线性次数；第二阶段各指针最多移动 $N$ 步即可相遇定位入口，总体的时间复杂度仍保持在线性级别。
• 空间复杂度：$O(1)$。全程我们只额外分配了 p1 和 p2 两个常数级别的指针变量，没有产生其他任何额外的内存开销。