LeetCode 142 环形链表 IILinked 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 判圈算法Floyds Cycle Detection Algorithm快慢指针分别以 2 步与 1 步前进用于检测环是否存在。环入口定位的数学证明Cycle Start Detection Math理解「为何相遇后把其中一个指针重置到头节点再以相同速度前进二者会在环入口再次相遇」。若你尚未掌握仅「判断是否有环」的解法可先阅读仓库中的姊妹篇 Linked List Cycle141题解 及其 Hint 文档再回到本文学习「定位环入口」的进阶部分。题目背景与约束根据 C 源码头注释本题的核心约束如下输入为单链表的头节点head要求返回环开始的节点若不存在环则返回null。环的存在性由内部参数pos表示tail.next所连接节点的 0 起始下标但pos不作为函数参数传入。节点数量范围[0, 10^4]节点值范围-10^5 Node.val 10^5pos为-1或链表内的合法下标。约定不得修改链表因此不能采用「标记已访问节点值」之类的破坏性手段。解法一哈希集合Hash Set直觉Intuition如果我们在遍历过程中第二次访问到同一个节点那么这个节点必然是环的起点——因为链表是单向的只有环的存在才会让遍历折返到已访问节点而折返点正是环的入口。用一个集合记录所有访问过的节点第一个「重复出现」的节点就是环的入口若遍历到链表末尾null仍未遇到重复节点则说明不存在环。算法步骤Algorithm创建一个哈希集合seen用于存放已访问节点。从头节点head开始遍历链表。对每个节点检查它是否已在集合中若是直接返回该节点作为环的起点。否则将该节点加入集合并移动到下一个节点。若遍历到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 NoneJava/** * 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) { SetListNode 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_setListNode* 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) { HashSetListNode seen new HashSetListNode(); 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 HashSetListNode() 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 SetObjectIdentifier() 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 // OptionBoxListNode 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: OptionBoxListNode) - OptionBoxListNode { // Cannot form a cycle with owned BoxListNode in safe Rust. None } }Rust 语言特例在安全 Rust 中BoxListNode是独占所有权模型无法构造共享引用意义上的环因此哈希集合方案在OptionBoxListNode签名下不可行。这也是仓库在 Rust 中更推荐快慢指针配合原始指针方案的原因详见下文解法二。时间与空间复杂度时间复杂度$O(n)$每个节点至多访问一次集合查找平均 $O(1)$。空间复杂度$O(n)$需要额外存储最多 $n$ 个节点引用。适用场景实现最简单、最直观代价是需要与链表等长的额外空间。若面试要求空间 $O(1)$则必须使用解法二。解法二快慢指针Floyd 判圈 环入口定位直觉IntuitionFloyd 判圈算法使用两个速度不同的指针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将slow与fast都初始化为head。循环推进slow走 1 步fast走 2 步直到二者相遇或fast到达链表末尾。若fast到达null含fast.next null的情况说明无环返回null。二者在环内相遇后将slow重置为head。两个指针同时以 1 步的速度前进直到再次相遇。返回该相遇点即为环的入口节点。多语言参考实现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 NoneJava/** * 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 OptionBoxListNode in safe Rust // because Box enforces unique ownership. In LeetCodes Rust environment, // cycle problems typically use raw pointers. Below is Floyds algorithm // translated using raw pointers, matching the Java logic. impl Solution { pub fn detect_cycle(head: OptionBoxListNode) - OptionBoxListNode { // With owned BoxListNode, 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 headfast保持不动然后二者同步走 1 步。陷阱四用节点值而不是节点引用比较该陷阱在 141 题解 中明确列出同样适用于本题的相遇判断。环检测必须比较两个指针是否指向同一个节点对象引用/地址相等而不是比较val是否相等。若用slow.val fast.val判断相遇两个值相同但位置不同的节点会触发错误命中。与 141「环形链表」的对比与进阶路径本题是 141. Linked List Cycle判断是否有环 的直接进阶对比维度141 环形链表hasCycle142 环形链表 IIdetectCycle输出布尔值是否存在环节点环的入口节点无环返回 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考