【LeetCode每日一题】141. 环形链表 142.环形链表 II

2025.8.29

141. 环形链表

题目

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

总体思路

快慢指针工作原理

这个算法使用Floyd判圈算法（龟兔赛跑算法）：

1. 两个指针：慢指针（每次1步）和快指针（每次2步）
2. 无环情况：快指针会先到达链表末尾（nil）
3. 有环情况：快指针最终会追上慢指针（在环内相遇）

数学证明

假设：

• 链表头部到环起点的距离：m
• 环的长度：n
• 快指针速度是慢指针的2倍

当慢指针进入环时，快指针已经在环中。由于速度差为1，快指针最多需要n步就能追上慢指针。

时间复杂度与空间复杂度

• 时间复杂度：O(n)
  • 最坏情况下需要遍历整个链表
  • 有环时会在O(n)时间内检测到
• 空间复杂度：O(1)
  • 只使用了两个指针变量
  • 不需要额外数据结构

代码

golang

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func hasCycle(head *ListNode) bool {// 如果链表为空或者只有一个节点，肯定没有环if head == nil || head.Next == nil {return false}// 初始化快慢指针，都指向头节点slow := headfast := head// 遍历链表，检测是否有环// 条件：fast和fast.Next都不为nil，确保可以安全移动for fast != nil && fast.Next != nil {slow = slow.Next      // 慢指针移动一步fast = fast.Next.Next // 快指针移动两步// 如果快慢指针相遇，说明有环if slow == fast {return true}}// 如果快指针到达链表末尾，说明没有环return false
}

func hasCycle(head *ListNode) bool {if head == nil || head.Next ==nil {return false}slow := headfast := headfor fast != nil && fast.Next != nil {fast = fast.Next.Nextslow = slow.Nextif fast == slow {return true}}return false
}

142. 环形链表 II

题目

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

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

示例 2：

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

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

总体思路

这个算法采用Floyd判圈算法（龟兔赛跑算法）来检测链表中的环并定位环的起始节点。算法分为两个阶段：

1. 检测阶段：使用快慢指针判断链表是否有环
2. 定位阶段：如果有环，找到环开始的位置

算法步骤

第一阶段：检测环的存在

• 慢指针每次移动1步，快指针每次移动2步
• 如果快慢指针相遇，说明有环
• 如果快指针到达链表末尾，说明无环

第二阶段：定位环起点

• 将慢指针重置到链表头部
• 快慢指针都以每次1步的速度移动
• 再次相遇的点就是环的起始节点

时间复杂度与空间复杂度

• 时间复杂度：O(n)
  • 检测阶段最多遍历n个节点
  • 定位阶段最多遍历n个节点
  • 总计：O(n) + O(n) = O(n)
• 空间复杂度：O(1)
  • 只使用了2个指针变量
  • 不需要额外的数据结构

代码

golang

/*** 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}panduan := falseslow := headfast := headfor fast != nil && fast.Next != nil {slow = slow.Nextfast = fast.Next.Nextif slow == fast {panduan = truebreak}}if !panduan {return nil}slow = headfor slow != fast {slow = slow.Nextfast = fast.Next}return slow
}

/*** 检测链表中的环并返回环的起始节点* 使用Floyd判圈算法（龟兔赛跑算法）* * @param head *ListNode 链表的头节点* @return *ListNode 环的起始节点，如果没有环返回nil*/
func detectCycle(head *ListNode) *ListNode {// 边界条件处理：// 1. 空链表肯定没有环// 2. 单节点链表（没有自环）也没有环if head == nil || head.Next == nil {return nil}// 初始化标志变量，用于记录是否检测到环hasCycle := false// 初始化快慢指针，都指向链表头节点slow := head  // 慢指针，每次移动1步fast := head  // 快指针，每次移动2步// 第一阶段：检测链表是否有环// 循环条件：确保fast和fast.Next不为nil，避免空指针异常for fast != nil && fast.Next != nil {// 慢指针移动1步slow = slow.Next// 快指针移动2步（这是算法的关键）// 快指针速度是慢指针的2倍，确保在有环情况下会相遇fast = fast.Next.Next// 如果快慢指针相遇，说明链表有环if slow == fast {hasCycle = true  // 设置标志位break           // 跳出循环}}// 如果没有检测到环，直接返回nilif !hasCycle {return nil}// 第二阶段：定位环的起始节点// 将慢指针重新指向链表头节点slow = head// 快慢指针都以每次1步的速度移动// 根据数学推导，它们会在环的起始节点相遇for slow != fast {slow = slow.Next  // 慢指针移动1步fast = fast.Next  // 快指针移动1步}// 返回环的起始节点（此时slow和fast指向同一个节点）return slow
}

小感悟

这两个环形链表用快慢指针好方便！
但是我还不会用别的方法，先学会这一种算了！