LeetCode 141: Linked List Cycle Solution in Python Explained

Problem Statement

In LeetCode 141, you’re given the head of a singly linked list where each node has a value and a next pointer. Your task is to return true if the list contains a cycle (a node’s next pointer eventually points back to a previous node), or false if it’s acyclic (ends with null). This differs from string segmentation like LeetCode 140: Word Break II, focusing on linked list traversal rather than string decomposition.

Constraints

• Number of nodes: 0 <= n <= 10^4
• Node values: -10^5 <= Node.val <= 10^5
• pos (cycle entry) is -1 (no cycle) or a valid index

Example

Let’s see some cases:

Copy codeInput: head = [3,2,0,-4], pos = 1
      3 -> 2 -> 0 -> -4
           ^          |
           |__________|
Output: true
Explanation: Cycle at 2 (index 1), -4 points back to 2.

Copy codeInput: head = [1,2], pos = 0
      1 -> 2
      ^    |
      |____|
Output: true
Explanation: Cycle at 1 (index 0), 2 points back to 1.

Copy codeInput: head = [1], pos = -1
      1 -> null
Output: false
Explanation: No cycle, ends at null.

These examples show we’re detecting loops in the list.

Understanding the Problem

How do you solve LeetCode 141: Linked List Cycle in Python? Take head = [3,2,0,-4], pos = 1. The list is 3->2->0->-4, with -4 pointing back to 2, forming a cycle, so return true. For [1], pos = -1, it’s 1->null, no cycle, so false. This isn’t a word break problem like LeetCode 139: Word Break; it’s about linked list cycle detection. We’ll use: 1. Floyd’s Cycle Detection: O(n) time, O(1) space—our best solution. 2. Hash Set: O(n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Floyd’s Cycle Detection Approach

Explanation

Floyd’s Cycle Detection (also known as the "tortoise and hare" algorithm) uses two pointers: a slow pointer moving one step and a fast pointer moving two steps. If there’s a cycle, they’ll eventually meet inside it due to their speed difference; if not, the fast pointer will reach the end (null). This is the best solution due to its O(n) time complexity, O(1) space usage (no extra data structures), and elegant use of pointer dynamics, making it both efficient and optimal.

For [3,2,0,-4], pos = 1:

• Slow: 3, Fast: 3.
• Slow: 2, Fast: 0.
• Slow: 0, Fast: 2 (wrapped).
• Slow: -4, Fast: 0 (meet), cycle detected.

Step-by-Step Example

Assume a ListNode class: class ListNode: def __init__(self, x): self.val = x; self.next = None.

Example 1: head = [3,2,0,-4], pos = 1

Goal: Return true.

• Setup: Cycle at 2: 3->2->0->-4->2.
• Start: slow = head (3), fast = head (3).
• Step 1: slow = 2, fast = 0.
• Step 2: slow = 0, fast = 2.
• Step 3: slow = -4, fast = 0.
• Step 4: slow = 2, fast = -4 (no meet yet).
• Step 5: slow = 0, fast = 2 (meet inside cycle).
• Finish: Meeting detected, return true.

Example 2: head = [1,2], pos = 0

Goal: Return true.

• Setup: 1->2->1.
• Start: slow = 1, fast = 1.
• Step 1: slow = 2, fast = 1.
• Step 2: slow = 1, fast = 1 (meet).
• Finish: Return true.

Example 3: head = [1], pos = -1

Goal: Return false.

• Setup: 1->null.
• Start: slow = 1, fast = 1.
• Step 1: slow = null, fast = null.
• Finish: Fast reaches null, return false.

How the Code Works (Floyd’s Cycle Detection) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codeclass ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def hasCycle(head: ListNode) -> bool:
    # Line 1: Handle null or single node cases
    if not head or not head.next:
        # If head is None or has no next (e.g., [1]), no cycle possible
        return False

    # Line 2: Initialize slow and fast pointers
    slow = head
    # Slow pointer starts at head (e.g., 3)
    fast = head
    # Fast pointer starts at head (e.g., 3)

    # Line 3: Traverse list with two speeds
    while fast and fast.next:
        # Continue while fast and its next exist (e.g., not null)

        # Line 4: Move slow pointer one step
        slow = slow.next
        # Advances one node (e.g., 3->2)

        # Line 5: Move fast pointer two steps
        fast = fast.next.next
        # Advances two nodes (e.g., 3->0)

        # Line 6: Check for meeting
        if slow == fast:
            # If pointers meet (e.g., both at 2), cycle exists
            return True

    # Line 7: Return false if fast reaches end
    return False
    # If fast hits null (e.g., acyclic list), no cycle

This detailed breakdown clarifies how Floyd’s algorithm efficiently detects cycles.

Alternative: Hash Set Approach

Explanation

Hash Set uses a set to store visited nodes, checking for duplicates as it traverses the list. If a node is revisited, there’s a cycle; if it reaches null, there isn’t. This is a practical alternative, straightforward with O(n) time, but uses O(n) space, making it less optimal than Floyd’s for space constraints.

For [3,2,0,-4], pos = 1:

• Visit 3, 2, 0, -4, 2 (duplicate), cycle detected.

Step-by-Step Example (Alternative)

For [3,2,0,-4], pos = 1:

• Start: visited = set().
• Step 1: Add 3, visited = {3}.
• Step 2: Add 2, visited = {3, 2}.
• Step 3: Add 0, visited = {3, 2, 0}.
• Step 4: Add -4, visited = {3, 2, 0, -4}.
• Step 5: 2 in visited, return true.
• Finish: Return true.

How the Code Works (Hash Set)

Copy codedef hasCycleHash(head: ListNode) -> bool:
    visited = set()
    curr = head
    while curr:
        if curr in visited:
            return True
        visited.add(curr)
        curr = curr.next
    return False

Complexity

• Floyd’s Cycle Detection:
• Time: O(n) – linear traversal with meeting.
• Space: O(1) – two pointers.
• Hash Set:
• Time: O(n) – single pass.
• Space: O(n) – hash set storage.

Efficiency Notes

Floyd’s Cycle Detection is the best solution with O(n) time and O(1) space, meeting optimal constraints elegantly—Hash Set matches time complexity but uses O(n) space, making it simpler but less space-efficient.

Key Insights

• Floyd’s: Speed difference detects loops.
• Hash Set: Tracks visited nodes.
• Cycle: Revisit indicates loop.

Additional Example

For head = [1,2,3], pos = 2:

• Goal: true.
• Floyd’s: Slow and fast meet at 3.

Edge Cases

• Empty List: [] → false.
• Single Node: [1] → false.
• No Cycle: [1,2] → false.

Both solutions handle these well.

Final Thoughts

LeetCode 141: Linked List Cycle in Python is a classic linked list challenge. The Floyd’s Cycle Detection solution shines with its efficiency and minimalism, while Hash Set offers an intuitive approach. Want more? Try LeetCode 142: Linked List Cycle II for cycle entry detection or LeetCode 94: Binary Tree Inorder Traversal for tree basics. Ready to practice? Solve LeetCode 141 on LeetCode with [3,2,0,-4] and pos = 1, aiming for true—test your skills now!