💬 Discord
Sign In
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.