LeetCode如何找出链表中环的入口节点

# LeetCode如何找出链表中环的入口节点

## 引言

在算法面试和编程竞赛中，链表相关的问题出现频率极高。其中，**检测链表中的环并找出环的入口节点**是一类经典问题，不仅考察对链表结构的理解，还涉及巧妙的算法设计。本文将系统性地讲解该问题的多种解法，从暴力法到最优解，逐步剖析背后的数学原理，并提供清晰的代码实现。

---

## 问题描述

LeetCode原题[142. Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii/)的描述如下：

> 给定一个链表的头节点 `head`，返回链表开始入环的第一个节点。如果链表无环，则返回 `null`。

**示例：**
```python
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为1的节点
解释：链表中有一个环，其尾部连接到第二个节点。

方法一：哈希表法（暴力解法）

核心思想

遍历链表中的每个节点，并将节点引用存入哈希表。当遇到已存在的节点时，该节点即为环的入口。

算法步骤

1. 初始化一个空的哈希集合 visited。
2. 遍历链表，对每个节点：
   • 若当前节点在 visited 中，返回该节点（环入口）。
   • 否则将节点加入 visited。
3. 若遍历结束未发现重复节点，返回 null。

复杂度分析

• 时间复杂度：O(n)，每个节点被访问一次。
• 空间复杂度：O(n)，最坏情况下需存储所有节点。

代码实现

def detectCycle(head):
    visited = set()
    while head:
        if head in visited:
            return head
        visited.add(head)
        head = head.next
    return None

方法二：快慢指针法（Floyd判圈算法）

核心思想

通过快慢指针判断链表是否有环，并利用数学推导找到环的入口节点。

算法步骤

1. 判断是否有环：
   • 快指针（fast）每次走两步，慢指针（slow）每次走一步。
   • 若两指针相遇，说明有环；若快指针到达末尾，则无环。
2. 寻找环入口：
   • 将快指针重新指向头节点，并改为每次走一步。
   • 快慢指针再次相遇的节点即为环入口。

数学推导

设链表头到环入口距离为 a，环入口到相遇点距离为 b，环剩余部分为 c。
根据快慢指针速度关系： - 慢指针路程：a + b - 快指针路程：a + b + k*(b + c)（k为整数）
由于快指针速度是慢指针的两倍：
2(a + b) = a + b + k(b + c)
化简得：a = (k-1)(b + c) + c
这意味着：从头节点和相遇点同时出发的两个指针，最终会在环入口相遇。

复杂度分析

• 时间复杂度：O(n)，线性遍历。
• 空间复杂度：O(1)，仅使用常数空间。

代码实现

def detectCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:  # 有环
            fast = head
            while fast != slow:
                fast = fast.next
                slow = slow.next
            return fast
    return None

方法对比

推荐：快慢指针法在空间复杂度上更优，是面试中的理想解法。

边界条件与注意事项

1. 空链表或单节点链表：直接返回 null。
2. 环在头节点：快慢指针首次相遇即满足条件。
3. 无环链表：快指针会先到达末尾。

扩展思考

如何计算环的长度？

1. 找到相遇点后，固定一个指针，另一个指针单步移动并计数，直到再次相遇。

如何判断环的入口是头节点？

• 若快慢指针首次相遇时，慢指针尚未完成一圈（即 a >= b + c），则环入口为头节点。

实际应用场景

1. 内存管理：检测循环引用。
2. 网络路由：发现路由环路。
3. 生物学：分析循环代谢路径。

总结

• 哈希表法直观但空间效率低，适合快速实现。
• 快慢指针法通过数学推导将空间复杂度优化至O(1)，是更优解。
• 理解背后的数学原理（路程关系）是掌握该问题的关键。

通过本文的详细讲解，读者应能熟练掌握检测链表环入口的两种方法，并灵活运用于实际编程问题中。

附录：相关LeetCode题目

1. 141. Linked List Cycle（判断是否有环）
2. 287. Find the Duplicate Number（类似快慢指针思想）

提示：多练习相关题目以加深对双指针技巧的理解。 “`