LeetCode 题解工作台
环形链表
给你一个链表的头节点 head ，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 注意： pos 不作为参数进行传递 。仅仅是为了标识链…
3
题型
5
代码语言
3
相关题
当前训练重点
简单 · 链表指针操作
答案摘要
我们可以遍历链表，用一个哈希表 记录每个节点。当某个节点二次出现时，则表示存在环，直接返回 `true`。否则链表遍历结束，返回 `false`。 时间复杂度 ，空间复杂度 。其中 是链表中的节点数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给你一个链表的头节点 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 <= 105pos为-1或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？
解题思路
方法一：哈希表
我们可以遍历链表，用一个哈希表 记录每个节点。当某个节点二次出现时，则表示存在环，直接返回 true。否则链表遍历结束，返回 false。
时间复杂度 ，空间复杂度 。其中 是链表中的节点数。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
s = set()
while head:
if head in s:
return True
s.add(head)
head = head.next
return False
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you notice what happens when the fast pointer laps the slow pointer in a cycle?
- question_mark
Can you optimize the solution to use constant space without losing correctness?
- question_mark
Will you consider edge cases such as a single node pointing to itself or an empty list?
常见陷阱
外企场景- error
Assuming pos is given and trying to access an index instead of following pointers.
- error
Forgetting to check null before advancing the fast pointer, causing runtime errors.
- error
Confusing node values with node identity; cycles depend on reference, not values.
进阶变体
外企场景- arrow_right_alt
Return the starting node of the cycle instead of a boolean to locate the loop entry.
- arrow_right_alt
Determine the cycle length once a cycle is detected to measure loop size.
- arrow_right_alt
Detect multiple cycles in a linked list if nodes form disconnected loops.