⚡Flashcard Drill➔
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

  1. Floyd's tortoise and hare: move a slow pointer one step and a fast pointer two steps per iteration.
  2. If there is a cycle, the fast pointer eventually laps the slow one and they meet.
  3. If there is no cycle, the fast pointer reaches None.
  4. 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 fast instead of fast and fast.next: fast.next.next would raise an AttributeError on the last node.
  • Comparing values instead of node identity: two distinct nodes can hold equal values, so slow == fast (identity) is required, not slow.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 at head.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 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