LeetCode 142 环形链表 II（Linked List Cycle II）全解：从哈希集合到 Floyd 双指针定位环入口

LeetCode 142 环形链表 II（Linked List Cycle II）全解：从哈希集合到 Floyd 双指针定位环入口

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本篇技术指南围绕 LeetCode 142「Linked List Cycle II」展开，讲解在 leetcode 仓库的 环形链表 II 题解 中给出的两种完整解法：哈希集合法与 Floyd 快慢指针法。文章不仅会逐语言呈现可运行的参考实现，还会结合仓库内 Java、C、Swift 的源码印证实现细节，并深入推导「相遇后重置指针即可定位环入口」的数学原理。读完本文，你将掌握从「判断有无环」到「返回环起始节点」的完整解题链，并理解两种解法在时间与空间复杂度上的权衡。

前置知识（Prerequisites）

在动手解决本题之前，建议先熟练掌握以下基础：

• 链表（Linked Lists）：遍历节点、理解指针（引用）的语义。本题所有操作都建立在next指针之上，且要求不得修改链表结构（见 C 源码注释）。
• 哈希集合（Hash Sets）：支持 O(1) 平均复杂度的查找，用于记录已访问节点。
• Floyd 判圈算法（Floyd's Cycle Detection Algorithm）：快慢指针分别以 2 步与 1 步前进，用于检测环是否存在。
• 环入口定位的数学证明（Cycle Start Detection Math）：理解「为何相遇后把其中一个指针重置到头节点，再以相同速度前进，二者会在环入口再次相遇」。

若你尚未掌握仅「判断是否有环」的解法，可先阅读仓库中的姊妹篇 Linked List Cycle（141）题解 及其 Hint 文档，再回到本文学习「定位环入口」的进阶部分。

题目背景与约束

根据 C 源码头注释，本题的核心约束如下：

• 输入为单链表的头节点head，要求返回环开始的节点；若不存在环则返回null。
• 环的存在性由内部参数pos表示（tail.next所连接节点的 0 起始下标），但pos不作为函数参数传入。
• 节点数量范围：[0, 10^4]；节点值范围：-10^5 <= Node.val <= 10^5；pos为-1或链表内的合法下标。
• 约定不得修改链表，因此不能采用「标记已访问节点值」之类的破坏性手段。

---

解法一：哈希集合（Hash Set）

直觉（Intuition）

如果我们在遍历过程中第二次访问到同一个节点，那么这个节点必然是环的起点——因为链表是单向的，只有环的存在才会让遍历折返到已访问节点，而折返点正是环的入口。用一个集合记录所有访问过的节点，第一个「重复出现」的节点就是环的入口；若遍历到链表末尾（null）仍未遇到重复节点，则说明不存在环。

算法步骤（Algorithm）

1. 创建一个哈希集合seen用于存放已访问节点。
2. 从头节点head开始遍历链表。
3. 对每个节点，检查它是否已在集合中：若是，直接返回该节点作为环的起点。
4. 否则，将该节点加入集合，并移动到下一个节点。
5. 若遍历到null，返回null（表示无环）。

多语言参考实现

以下是 linked-list-cycle-ii.md 中给出的各语言哈希集合实现。核心思路完全一致：以「节点引用/对象标识」作为判重依据，而不是节点值。

Python

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: seen = set() cur = head while cur: if cur in seen: return cur seen.add(cur) cur = cur.next return None

Java

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { Set<ListNode> seen = new HashSet<>(); ListNode cur = head; while (cur != null) { if (seen.contains(cur)) { return cur; } seen.add(cur); cur = cur.next; } return null; } }

C++

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* detectCycle(ListNode* head) { unordered_set<ListNode*> seen; ListNode* cur = head; while (cur) { if (seen.find(cur) != seen.end()) { return cur; } seen.insert(cur); cur = cur->next; } return nullptr; } };

JavaScript

/** * Definition for singly-linked list. * class ListNode { * constructor(val = 0, next = null) { * this.val = val; * this.next = next; * } * } */ class Solution { /** * @param {ListNode} head * @return {ListNode} */ detectCycle(head) { const seen = new Set(); let cur = head; while (cur) { if (seen.has(cur)) { return cur; } seen.add(cur); cur = cur.next; } return null; } }

C#

/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode DetectCycle(ListNode head) { HashSet<ListNode> seen = new HashSet<ListNode>(); ListNode cur = head; while (cur != null) { if (seen.Contains(cur)) { return cur; } seen.Add(cur); cur = cur.next; } return null; } }

Go

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func detectCycle(head *ListNode) *ListNode { seen := make(map[*ListNode]bool) cur := head for cur != nil { if seen[cur] { return cur } seen[cur] = true cur = cur.Next } return nil }

Kotlin

/** * Example: * var li = ListNode(5) * var v = li.`val` * Definition for singly-linked list. * class ListNode(var `val`: Int) { * var next: ListNode? = null * } */ class Solution { fun detectCycle(head: ListNode?): ListNode? { val seen = HashSet<ListNode>() var cur = head while (cur != null) { if (cur in seen) { return cur } seen.add(cur) cur = cur.next } return null } }

Swift

/** * Definition for singly-linked list. * public class ListNode { * public var val: Int * public var next: ListNode? * public init(_ val: Int) { * self.val = val * self.next = nil * } * } */ class Solution { func detectCycle(_ head: ListNode?) -> ListNode? { var seen = Set<ObjectIdentifier>() var cur = head while let node = cur { let id = ObjectIdentifier(node) if seen.contains(id) { return node } seen.insert(id) cur = node.next } return nil } }

Swift 实现要点：Swift 的Set需要元素遵循Hashable，而ListNode是类对象。这里使用ObjectIdentifier(node)（基于对象内存地址的唯一标识）作为集合元素，等价于其他语言中「按引用判重」的语义。

Rust（注意说明）

// Note: Cycle detection via HashSet is not directly possible with // Option<Box<ListNode>> in safe Rust since Box provides unique // ownership (no shared references to track identity). // See the fast & slow pointer approach for the idiomatic solution. impl Solution { pub fn detect_cycle(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> { // Cannot form a cycle with owned Box<ListNode> in safe Rust. None } }

Rust 语言特例：在安全 Rust 中，Box<ListNode>是独占所有权模型，无法构造共享引用意义上的环，因此哈希集合方案在Option<Box<ListNode>>签名下不可行。这也是仓库在 Rust 中更推荐快慢指针（配合原始指针）方案的原因，详见下文解法二。

时间与空间复杂度

• 时间复杂度：$O(n)$，每个节点至多访问一次，集合查找平均 $O(1)$。
• 空间复杂度：$O(n)$，需要额外存储最多 $n$ 个节点引用。

适用场景：实现最简单、最直观；代价是需要与链表等长的额外空间。若面试要求空间 $O(1)$，则必须使用解法二。

---

解法二：快慢指针（Floyd 判圈 + 环入口定位）

直觉（Intuition）

Floyd 判圈算法使用两个速度不同的指针：fast每次前进 2 步，slow每次前进 1 步。若存在环，fast最终会在环内「追上」slow，二者相遇。关键洞察是数学上的：相遇时，把其中一个指针重置回head，然后两个指针都以 1 步的速度前进，它们再次相遇的位置就是环的起点。这是因为「头节点到环入口的距离」恰好等于「相遇点到环入口的距离（沿环方向）」。

为什么相遇后重置指针就能找到环入口（数学推导）

设：

• 链表头到环入口的距离为 $a$（不含环入口节点本身的步数）；
• 环的长度为 $b$；
• 快慢指针第一次相遇时，slow在环内已走过的距离为 $x$（$0 \le x < b$）。

当slow刚进入环时，fast已经在环内绕行。二者第一次相遇时：

• slow共走了 $a + x$ 步；
• fast共走了 $2(a + x)$ 步。

由于fast比slow多走的距离恰为环长的整数倍（fast至少多绕环一圈）：

$$ 2(a + x) - (a + x) = a + x = k \cdot b \quad (k \ge 1) $$

即 $a + x$ 是环长 $b$ 的整数倍。整理得：

$$ a = k \cdot b - x $$

这等价于：从相遇点继续沿环走 $a$ 步，恰好回到环入口（因为 $a \bmod b = (k \cdot b - x) \bmod b = b - x$，而从相遇点沿环走到环入口的距离正是 $b - x$）。

因此，将slow重置到头节点后，两个指针各走 $a$ 步：一个从头节点走到环入口，另一个从相遇点沿环走到环入口——二者必然在环入口再次相遇。这正是第二阶段的数学依据。

算法步骤（Algorithm）

1. 将slow与fast都初始化为head。
2. 循环推进：slow走 1 步，fast走 2 步，直到二者相遇，或fast到达链表末尾。
3. 若fast到达null（含fast.next == null的情况），说明无环，返回null。
4. 二者在环内相遇后，将slow重置为head。
5. 两个指针同时以 1 步的速度前进，直到再次相遇。
6. 返回该相遇点，即为环的入口节点。

多语言参考实现

Python

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head or not head.next: return None slow, fast = head, head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: slow = head while slow != fast: slow = slow.next fast = fast.next return slow return None

Java

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { if (head == null || head.next == null) { return null; } ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; } } return null; } }

C++

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* detectCycle(ListNode* head) { if (!head || !head->next) { return nullptr; } ListNode* slow = head; ListNode* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; } } return nullptr; } };

JavaScript

/** * Definition for singly-linked list. * class ListNode { * constructor(val = 0, next = null) { * this.val = val; * this.next = next; * } * } */ class Solution { /** * @param {ListNode} head * @return {ListNode} */ detectCycle(head) { if (!head || !head.next) { return null; } let slow = head, fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; if (slow === fast) { slow = head; while (slow !== fast) { slow = slow.next; fast = fast.next; } return slow; } } return null; } }

C#

/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode DetectCycle(ListNode head) { if (head == null || head.next == null) { return null; } ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; } } return null; } }

Go

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func detectCycle(head *ListNode) *ListNode { if head == nil || head.Next == nil { return nil } 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 }

Kotlin

/** * Example: * var li = ListNode(5) * var v = li.`val` * Definition for singly-linked list. * class ListNode(var `val`: Int) { * var next: ListNode? = null * } */ class Solution { fun detectCycle(head: ListNode?): ListNode? { if (head?.next == null) { return null } var slow = head var fast = head while (fast?.next != null) { slow = slow?.next fast = fast.next?.next if (slow == fast) { slow = head while (slow != fast) { slow = slow?.next fast = fast?.next } return slow } } return null } }

Swift

/** * Definition for singly-linked list. * public class ListNode { * public var val: Int * public var next: ListNode? * public init(_ val: Int) { * self.val = val * self.next = nil * } * } */ class Solution { func detectCycle(_ head: ListNode?) -> ListNode? { if head == nil || head?.next == nil { return nil } var slow = head var fast = head while fast != nil && fast?.next != nil { slow = slow?.next fast = fast?.next?.next if slow === fast { slow = head while slow !== fast { slow = slow?.next fast = fast?.next } return slow } } return nil } }

Swift 实现要点：类实例的相等性必须用引用同一性运算符===/!==判断，而不能用==（后者在ListNode未遵循Equatable时不可用）。Kotlin 的==在可空引用类型上自动退化为引用比较，语义一致。

Rust（原始指针版思路）

// Note: A true cycle cannot exist with Option<Box<ListNode>> in safe Rust // because Box enforces unique ownership. In LeetCode's Rust environment, // cycle problems typically use raw pointers. Below is Floyd's algorithm // translated using raw pointers, matching the Java logic. impl Solution { pub fn detect_cycle(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> { // With owned Box<ListNode>, cycles cannot form in safe Rust. // If using raw pointers (*mut ListNode), the algorithm is: // let mut slow = head_ptr; // let mut fast = head_ptr; // while !fast.is_null() && unsafe { (*fast).next } != std::ptr::null_mut() { // slow = unsafe { (*slow).next }; // fast = unsafe { (*(*fast).next).next }; // if slow == fast { // slow = head_ptr; // while slow != fast { // slow = unsafe { (*slow).next }; // fast = unsafe { (*fast).next }; // } // return Some(slow); // the cycle start node // } // } // None None } }

时间与空间复杂度

• 时间复杂度：$O(n)$。第一阶段快慢指针至多遍历 $O(n)$ 个节点；第二阶段两个指针合计也至多走 $O(n)$ 步。
• 空间复杂度：$O(1)$ 额外空间，仅使用两个指针变量。

---

仓库源码印证：两种代码组织风格

在仓库中，解法二的实现存在两种组织风格，逻辑完全等价，可作为交叉验证：

风格一：循环内直接返回（与本文题解一致）

C 语言实现 在检测到fast == slow后，直接在循环内部完成第二阶段：

struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *fast = head; struct ListNode *slow = head; if (!head) return NULL; while (fast->next && fast->next->next) { fast = fast->next->next; slow = slow->next; if (fast == slow) { /** * The index of the node cycle is located the same number of nodes * away from the start of the linked list and the intersection of * the slow and fast pointers. */ struct ListNode *head_node = head; struct ListNode *intersection = slow; while (head_node != intersection) { head_node = head_node->next; intersection = intersection->next; } return intersection; } } return NULL; }

该实现值得注意的细节：

• 循环条件是fast->next && fast->next->next，即先确认fast可以安全前进两步再移动，避免解引用空指针。
• 第二阶段的head_node与intersection分别对应「从头节点出发」与「从相遇点出发」的两个指针，二者相遇处即环入口；其注释也直接点明了「链表头到环入口的距离等于相遇点到环入口的距离」这一数学事实。
• 循环结束后返回NULL，覆盖了「空链表」「单节点无环」等所有无环情形。

风格二：先 break 再统一判断（仓库 Java / Swift 实现）

Java 实现 与 Swift 实现 采用「相遇即break，循环外再做无环判断」的结构：

public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { break; } } if (fast == null || fast.next == null) { return null; } ListNode slow2 = head; while (slow != slow2) { slow = slow.next; slow2 = slow2.next; } return slow; } }

该风格的要点：

• 循环退出有两种可能：**相遇（break跳出）**或fast到达末尾（无环）。
• 循环外通过fast == null || fast.next == null区分这两种情形：满足即无环，返回null；否则说明确实相遇，进入第二阶段。
• 第二阶段引入新指针slow2（从head出发）与停留在相遇点的slow同步前进，避免了复用变量带来的语义混淆。

两种风格在时空复杂度上完全一致，选择哪种取决于编码习惯；理解「退出循环后的状态如何被二次判断」是读懂这类代码的关键。

---

常见陷阱（Common Pitfalls）

陷阱一：把第一次相遇点当作环入口返回

快慢指针第一次相遇的节点位于环内，但并不一定是环的起始节点（当环入口到相遇点的距离不为 0 时）。必须执行第二阶段：将其中一个指针重置为head，两个指针同时每次前进 1 步，直到再次相遇，此时的位置才是真正的环入口。

陷阱二：遗漏无环链表的处理

若fast到达null，说明链表无环，函数应返回null。如果跳过这一检查直接进入第二阶段，会在「环根本不存在」的情况下尝试寻找环入口，导致空指针异常（Null Pointer Exception）或无限循环。无论是「循环内直接返回」还是「break 后统一判断」的写法，都必须保留这一出口。

陷阱三：第二阶段指针重置错误

检测到相遇点后，必须只重置其中一个指针到头节点，另一个指针留在相遇点。常见错误包括：

• 把两个指针都重置回head——这会让第二阶段立刻「相遇」在head，返回错误结果；
• 把指针重置到错误的节点位置——导致第二阶段永远找不到正确入口甚至死循环。

正确做法：slow = head，fast保持不动，然后二者同步走 1 步。

陷阱四：用节点值而不是节点引用比较

（该陷阱在 141 题解 中明确列出，同样适用于本题的相遇判断。）环检测必须比较两个指针是否指向同一个节点对象（引用/地址相等），而不是比较val是否相等。若用slow.val == fast.val判断相遇，两个值相同但位置不同的节点会触发错误命中。

---

与 141「环形链表」的对比与进阶路径

本题是 141. Linked List Cycle（判断是否有环） 的直接进阶：

对比维度	141 环形链表（hasCycle）	142 环形链表 II（detectCycle）
输出	布尔值：是否存在环	节点：环的入口节点（无环返回 null）
哈希集合法	遇到重复节点返回true	遇到重复节点返回该节点
快慢指针法	相遇即返回true	相遇后还需第二阶段定位入口
复杂度	两种解法均为 $O(n)$ 时间	两种解法均为 $O(n)$ 时间（空间 $O(n)$ 或 $O(1)$）

从仓库的 Hint 文档 可以看到，141 的推荐目标是 $O(n)$ 时间、$O(1)$ 空间；142 在此基础上更进一步，要求精确定位环入口节点，这正对应快慢指针法的第二阶段。建议按「先会 141、再攻克 142」的顺序学习，把相遇检测与数学推导分开掌握。

小结

• 哈希集合法：直观、易于实现，时间 $O(n)$、空间 $O(n)$；核心是「第一次重复访问的节点即环入口」。
• 快慢指针法（Floyd）：时间 $O(n)$、空间 $O(1)$；核心是两阶段流程——先检测相遇，再利用「头到入口距离 = 相遇点到入口距离」的数学性质定位入口。
• 实现细节：注意无环情形的出口、第二阶段只重置一个指针、以及用引用相等而非值相等做比较。
• 仓库对照：可结合 C 实现、Java 实现 与 Swift 实现 观察两种等价的代码组织风格，加深对算法状态机的理解。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode