essay
hot100-环形链表I和II
#算法
hot100——环形链表I和II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
解
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
// detectCycle 检测链表中是否存在环，若存在则返回环的入口节点，否则返回 nil
func detectCycle(head *ListNode) *ListNode {
// 初始化快慢指针，都从链表头开始
slow, fast := head, head
// 使用快慢指针检测是否存在环
// 循环条件：fast 和 fast.Next 都不能为 nil，确保 fast.Next.Next 安全访问
for fast != nil && fast.Next != nil {
slow = slow.Next // 慢指针每次走 1 步
fast = fast.Next.Next // 快指针每次走 2 步
// 如果快慢指针相遇，说明链表中存在环
if slow == fast {
// 此时 slow（或 fast）是环内的某个相遇点
// 根据 Floyd 算法第二阶段：找环入口
// 将 curr 指针重置到链表头部
curr := head
// curr 从头开始，slow 从相遇点开始，两者以相同速度（每次1步）前进
// 它们第一次相遇的位置就是环的入口节点
for curr != slow {
curr = curr.Next
slow = slow.Next
}
// 返回环的入口节点
return curr
}
}
// 如果循环正常结束（fast 走到 nil），说明链表无环
return nil
}