给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 不允许修改 链表。

这个问题是经典的 **链表中环的检测与入口查找问题**，要求我们： - 判断链表是否有环； - 如果有环，返回环的入口节点； - 不能修改链表； - 时间复杂度 O(n)，空间复杂度 O(1)。 --- ## ✅ 解题思路（双指针法） 我们可以使用 **快慢指针法（Floyd 判圈算法）** 来解决这个问题： ### 第一步：判断是否有环 - 定义两个指针 `slow` 和 `fast`，初始都指向 `head`。 - `slow` 每次走一步，`fast` 每次走两步。 - 如果链表有环，它们最终会相遇； - 如果没有环，`fast` 或 `fast.next` 会变成 `None`。 ### 第二步：找到环的入口节点 - 当快慢指针相遇后，将 `slow` 重置为 `head`。 - 然后 `slow` 和 `fast` 每次都走一步。 - 当它们再次相遇时，相遇点就是环的入口。 --- ## ✅ 完整 Python 代码 ```python class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def detectCycle(self, head: ListNode) -> ListNode: if not head or not head.next: return None # Step 1: 判断是否有环 slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: # Step 2: 找到环的入口 slow = head while slow != fast: slow = slow.next fast = fast.next return slow # 无环 return None ``` --- ## ✅ 图解说明 假设链表如下： ``` A → B → C → D → E ↑ ↓ ↖ ← F ← G ``` - A 到 C 是无环部分； - C 到 G 是环； - C 是环的入口。 设： - A 到 C 距离为 `a` - C 到 F（相遇点）为 `b` - F 到 C 为 `c` 当 `slow` 和 `fast` 相遇时： - `slow` 走了 `a + b` - `fast` 走了 `a + b + n(b + c)`（因为绕了 n 圈） 由于 `fast` 是 `slow` 速度的两倍： ``` 2(a + b) = a + b + n(b + c) => a + b = n(b + c) => a = (n - 1)(b + c) + c ``` 所以当 `slow` 从 head 出发，`fast` 从相遇点出发，每次走一步，最终会在环入口相遇。 --- ## ✅ 示例测试代码 ```python # 创建链表 def create_cycle_list(values, pos): nodes = [ListNode(v) for v in values] for i in range(len(nodes) - 1): nodes[i].next = nodes[i+1] if pos >= 0: nodes[-1].next = nodes[pos] return nodes[0] # 测试 head = create_cycle_list([3, 2, 0, -4], 1) sol = Solution() entry = sol.detectCycle(head) print(entry.val if entry else "No cycle") # 输出: 2 ``` ---