环形链表 II

难度：⭐⭐⭐ 面试高频

考点

• Floyd 快慢指针判圈法
• 数学推导找环入口
• 字节面试高频题

题目描述

给定一个链表的头节点 head，如果链表中有环，返回环的入口节点。如果链表无环，返回 nil。

函数签名

func detectCycle(head *ListNode) *ListNode

示例

输入：3 -> 2 -> 0 -> -4 -> (回到 2)
输出：节点 2（环的入口）

输入：1 -> 2 -> nil
输出：nil（无环）

要求

1. 时间复杂度 O(n)，空间复杂度 O(1)（不能用哈希表）
2. 不能修改链表结构

提示

1. 快慢指针相遇 → 有环
2. 相遇后，一个指针回到 head，两个都走一步，再次相遇即为入口
3. 数学证明：设环前长度 a，环长 b，相遇时慢指针走了 a+k，快指针走了 a+k+nb，则 a+k = nb → a = nb-k = (n-1)b + (b-k)

---

参考答案（Go）

点击展开参考答案

//go:build ignore

package answer

type ListNode struct {
	Val  int
	Next *ListNode
}

func detectCycle(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			slow = head
			for slow != fast {
				slow = slow.Next
				fast = fast.Next
			}
			return slow
		}
	}
	return nil
}