NeetCode #305LC-141EasyLinked ListBlind 75NC 150NC 250
← Back to All Problems#305 · #141 · Linked List Cycle(环形链表)
📌 Problem Statement & Constraints
Given the head of a linked list, determine whether the list contains a cycle. Return
true if some node can be reached again by following next pointers. Constraints: the number of nodes is in [0, 10^4]. The follow-up asks for O(1) memory.💡 Core Algorithmic Approaches
- Floyd's tortoise and hare: move a slow pointer one step and a fast pointer two steps per iteration.
- If there is a cycle, the fast pointer eventually laps the slow one and they meet.
- If there is no cycle, the fast pointer reaches
None. - This uses O(1) extra space, unlike the hash-set approach.
💻 Benchmark Python3 Implementation
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow = fast = head
while fast and fast.next: # fast must have two steps available
slow = slow.next
fast = fast.next.next
if slow == fast:
return True # they met -> cycle
return False⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): with a cycle, the fast pointer closes the gap within O(n) steps; without one, it traverses the list once.
💾 Space Complexity
O(1): two pointers.
⚠️ Interview Pitfalls & Follow-ups
- Checking
fastinstead offast and fast.next:fast.next.nextwould raise anAttributeErroron the last node. - Comparing values instead of node identity: two distinct nodes can hold equal values, so
slow == fast(identity) is required, notslow.val == fast.val. - Using a hash set of visited nodes: correct and O(n) time, but O(n) space, which the follow-up forbids.
- Starting
fast = head.next: it works, but the standard formulation starts both athead.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Linked List Problems
中文速览与面试要点
环形链表
给你一个链表的头节点 head,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。如果链表中存在环,则返回 true;否则,返回 false。约束:链表中节点的数目范围是 [0, 10^4];-10^5 ≤ Node.val ≤ 10^5;pos 为 −1 或链表中的有效索引。
核心要点
- Floyd 判圈算法(快慢指针,标准解) :慢指针每次走 1 步,快指针每次走 2 步。若存在环,两者必然在环内相遇;若无环,快指针会先到达 None。
- 为什么必然相遇 :进入环后,快指针相对慢指针的速度为 1 步/轮,因此每轮把两者的距离缩小 1,最终距离降为 0(追上)。
- 空间 O(1) 的优势 :哈希表记录访问过的节点也能判环,但需要 O(n) 空间。
- 循环条件 : while fast and fast.next ——快指针必须能走两步,因此两个条件都要判断。
常见陷阱
- 循环条件只写 while fast : fast.next.next 在 fast.next 为 None 时会抛 AttributeError。必须同时判断 fast.next 。
- 用 slow.val == fast.val 判断相遇 :值相同不代表是同一节点(链表中可能有重复值)。必须用 is 比较对象身份。
- 先移动再判断的顺序 :必须先移动再比较;若先比较再移动,会漏掉「头节点即构成环」的情况(不过本解中初始时 slow 与 fast 都是 head,若先比较会立刻返回 True 而错误)。
- 用哈希集合记录访问节点 :正确但需要 O(n) 空间。
参考实现
class Solution:
def hasCycle(self, head: 'ListNode') -> bool:
slow = fast = head
while fast and fast.next: # 快指针能走两步
slow = slow.next # 慢指针走 1 步
fast = fast.next.next # 快指针走 2 步
if slow is fast: # 相遇 -> 有环
return True
return False