# 题目描述： 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 不允许修改 链表。 示例：
> 输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。 ## 思路分析： 方法一：（哈希表） 想找到环节点，那么就是在遍历的过程中出现第二次的节点，那么就在遍历的时候使用哈希表记录节点出现的频率，如果等于2，就说明这是环节点。
点击查看代码
``` func detectCycle(head *ListNode) *ListNode { if head == nil { return nil } nodeFlag:=make(map[*ListNode]int) for head!=nil{ nodeFlag[head]++ if nodeFlag[head]>1 { return head }else { head = head.Next } } return nil } ```方法二：快慢指针
x1：链表 head 到环的一个点需要 x1 步
x2:从环的第一个点到相遇点需要 x2 步
x3:从环中相遇点回到环的第一个点需要 x3 步
x2+x3:环的总长度
当相遇时，快慢指针的路程关系：
fast: t = (x1 + x2 + x3 + x2) / 2
slow: t = (x1 + x2) / 1
x1 + x2 + x3 + x2 = 2 * (x1 + x2)
所以 x1 = x3
所以用相同的速度走，一个从head出发，一个从相遇点出发并且按照相同的速度，必然会在环的入口相遇。
点击查看代码
func detectCycle(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return nil
}
fast, slow := head, head
// 快慢指针寻找环
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
if fast == slow {
// 找到环后重新初始化慢指针为头节点
slow = head
// 两指针相遇即为环入口
while fast != slow {
fast = fast.Next
slow = slow.Next
}
return slow
}
}
return nil // 如果没有环，返回nil
}