环形链表 II
Linked List Cycle II
本机进度仅保存在当前浏览器
题目描述
给定一个链表，返回链表开始入环的第一个节点；无环则返回 null。要求 O(1) 空间且不修改链表。
示例：3 -> 2 -> 0 -> -4，尾节点指向下标 1 的节点，环入口是值为 2 的节点。
解题思路
- 先用快慢指针判定有环并拿到相遇点（同第 141 题做法）。
- 数学推导：设头到入口距离 a，入口到相遇点距离 b，环长为 c。相遇时慢指针走 a + b，快指针走 a + b + k·c。
- 由"快指针步数是慢指针两倍"得 a = c - b + (k-1)·c，即从头到入口的距离等于从相遇点继续走到入口的距离。
- 因此相遇后把一个指针放回头部，两指针同速前进，再次相遇处就是环入口。
参考实现
查看参考实现Python · 建议先自行作答
def detectCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
# 相遇后同速前进，再次相遇点即环入口
p = head
while p is not slow:
p = p.next
slow = slow.next
return p
return None