LeetCode-Go 题解142. Linked List Cycle II 环形链表 II——快慢指针定位环入口的 Go 实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文基于 LeetCode-Go 仓库中 0142.Linked-List-Cycle-II 题解文档 展开完整讲解 LeetCode 第 142 题「环形链表 II」的解题思路与 Go 实现。这道题在 141 题判断链表是否有环的基础上更进一步不仅要判断链表是否存在环还要求在不使用额外空间、且不修改链表的前提下输出环的入口节点。读完本文你将掌握快慢指针Floyd 判圈算法的数学原理、如何通过一次相遇推导出环入口位置以及 LeetCode-Go 仓库中该题解在源码与测试层面的完整落地方式。题目描述给定一个链表返回链表开始入环的第一个节点。如果链表无环则返回null。为了表示给定链表中的环题目使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意不允许修改给定的链表。示例 1输入head [3,2,0,-4], pos 1 输出tail connects to node index 1 解释链表中有一个环其尾部连接到第二个节点。示例 2输入head [1,2], pos 0 输出tail connects to node index 0 解释链表中有一个环其尾部连接到第一个节点。示例 3输入head [1], pos -1 输出no cycle 解释链表中没有环。题目大意判断链表是否有环不能使用额外的空间。如果有环输出环的起点指针如果没有环则输出空nil。解题思路本题是 141. Linked List Cycle环形链表 的加强版在判断是否有环的基础上还需要输出环的第一个节点。快慢指针判环的原理经典的做法是使用快慢指针fast指针每次走 2 步slow指针每次走 1 步。如果链表存在环两个指针最终必定会在环内相遇如果链表无环fast指针会先到达链表末尾nil。为了推导出环入口的位置可以这样建模令从链表head走到环的入口节点需要x1步从环入口节点走到快慢指针相遇点需要x2步从相遇点继续沿链表方向走回环入口节点需要x3步。那么环的总长度就是x2 x3步。由于fast和slow相遇说明二者运动的时间相同因此它们走过的路程之间存在如下关系fast 的时间 t (x1 x2 x3 x2) / 2 slow 的时间 t (x1 x2) / 1 x1 x2 x3 x2 2 * (x1 x2) 所以 x1 x3关键结论从链表头到环入口的距离x1恰好等于从相遇点继续走到环入口的距离x3。利用 x1 x3 定位环入口基于上面的推导定位环入口的算法非常简洁先用快慢指针找出相遇点同时确定链表是否有环相遇后让fast指针回到链表的起点headslow指针停留在相遇点此后两个指针都每次只走 1 步继续前进因为x1 x3两个指针必定会在环的入口节点处再次相遇输出该节点即是最终结果。复杂度分析时间复杂度O(n)其中n为链表节点数。快慢指针相遇前slow指针最多走过环外的长度与环内一圈以内的距离整体仍为线性时间空间复杂度O(1)全程只使用两个指针变量没有借助哈希表等额外存储满足题目「不能使用额外的空间」的约束。Go 实现仓库源码解读LeetCode-Go 仓库在 leetcode/0142.Linked-List-Cycle-II/142. Linked List Cycle II.go 中给出了完整实现。源码通过type ListNode structures.ListNode类型别名复用了 structures 包中定义的单链表节点结构避免了重复定义package leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // ListNode define type ListNode structures.ListNode /** * 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 } isCycle, slow : hasCycle142(head) if !isCycle { return nil } fast : head for fast ! slow { fast fast.Next slow slow.Next } return fast } func hasCycle142(head *ListNode) (bool, *ListNode) { fast : head slow : head for slow ! nil fast ! nil fast.Next ! nil { fast fast.Next.Next slow slow.Next if fast slow { return true, slow } } return false, nil }实现细节拆解边界处理入口处首先判断head nil || head.Next nil链表为空或只有一个节点时不可能成环直接返回nil。这与 141 题的判环思路一致判环辅助函数hasCycle142从head同时出发fast每次前进两步、slow每次前进一步。循环终止条件是slow、fast、fast.Next任一为nil说明链表走到了尽头、无环若中途fast slow说明二者在环内相遇返回(true, slow)其中slow就是相遇节点二次相遇定位入口确认有环后将fast重置为headslow保持在相遇点二者同时每次走一步。根据上文推导的x1 x3它们一定在环入口处相遇此时fast与slow相同即为环的入口节点。链表节点的底层定义上述实现依赖的链表节点定义在 structures/ListNode.go 中是整个 LeetCode-Go 仓库链表题解共用的基础设施// ListNode 是链接节点 // 这个不能复制到*_test.go文件中。会导致Travis失败 type ListNode struct { Val int Next *ListNode }仓库还提供了配套的链表构造与转换工具例如Ints2List将[]int转为链表和List2Ints将链表转回[]int内置 100 层深度上限用于防御环状链表导致死循环。其中与本道题关系最密切的是Ints2ListWithCycle它可以直接构造出题目中描述的带环链表// Ints2ListWithCycle returns a list whose tail point to pos-indexed node // heads index is 0 // if pos -1, no cycle func Ints2ListWithCycle(nums []int, pos int) *ListNode { head : Ints2List(nums) if pos -1 { return head } c : head for pos 0 { c c.Next pos-- } tail : c for tail.Next ! nil { tail tail.Next } tail.Next c return head }从源码结构看该函数先把整数切片构造成普通单链表然后根据pos定位到环入口节点再把链表的尾节点Next指向该节点从而精确复现题目的三种场景pos 1示例 1、pos 0示例 2、pos -1无环示例 3。测试用例验证仓库为本题编写了完整的表驱动测试见 leetcode/0142.Linked-List-Cycle-II/142. Linked List Cycle II_test.go。测试用例覆盖了全部三个官方示例并额外补充了无环与空链表的边界情况输入nums输入pos期望结果[3, 2, 0, -4]1有环环入口节点值为2[1, 2]0有环环入口节点值为1[1]-1无环返回nil[1, 2, 3]-1无环返回nil[]-1空链表返回nil测试通过structures.Ints2ListWithCycle(p.nums, p.pos)构造链表再调用detectCycle(head)验证返回值预期有环时校验入口节点值是否匹配预期无环时校验返回是否为nil。这 5 组用例与文档中的示例一一对应同时覆盖了空链表等极端输入保证了实现的正确性。此外structures/ListNode_test.go 中的Test_Ints2ListWithCycle用例还对环构造工具本身进行了验证pos -1时返回普通链表、pos 1时尾部回指确保测试数据构造的可靠性。小结LeetCode 142 题的核心价值在于在 141 题「仅判环」的基础上借助一次简单的数学推导x1 x3把「找环入口」的问题转化为「两个同速指针的第二次相遇」全程只需常数级额外空间。LeetCode-Go 仓库通过 题解文档、Go 实现 与 表驱动测试 三部分完整呈现了这道题的解法其快慢指针思想与数学推导也可迁移到其他链表环类问题中是链表算法面试中必须掌握的基础模型。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考