LeetCode 142: Linked List Cycle II Solution in Python Explained

Problem Statement

In LeetCode 142, 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 the node where a cycle begins (if present)—the node a tail pointer points back to—or null if the list is acyclic (ends with null). This builds on LeetCode 141: Linked List Cycle, which detects cycles, to finding the entry point, differing from string segmentation like LeetCode 140: Word Break II.

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: Node 2
Explanation: Cycle begins at 2 (index 1), -4 points back to 2.

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

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

These examples show we’re locating the cycle’s start.

Understanding the Problem

How do you solve LeetCode 142: Linked List Cycle II in Python? Take head = [3,2,0,-4], pos = 1. The list is 3->2->0->-4, with -4 pointing back to 2, so the cycle starts at 2—return that node. For [1], pos = -1, it’s 1->null, no cycle, so null. This extends LeetCode 141, moving from detection to pinpointing the entry, unlike path sums in LeetCode 113: Path Sum II. We’ll use: 1. Floyd’s Cycle Detection with Entry Point: O(n) time, O(1) space—our best solution. 2. Hash Set with Tracking: O(n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Floyd’s Cycle Detection with Entry Point Approach

Explanation

Floyd’s Cycle Detection with Entry Point (tortoise and hare algorithm) uses two phases: 1. Detection: A slow pointer (one step) and fast pointer (two steps) meet inside the cycle if one exists. 2. Entry Point: Reset slow to head, move both at one step; they meet at the cycle’s entry due to mathematical properties (distance relationships in a loop).

This is the best solution due to its O(n) time complexity, O(1) space usage (no extra structures), and elegant use of pointer dynamics, making it both efficient and optimal.

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

• Meet at 0.
• Reset slow to 3, move both, meet at 2 (entry).

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 Node 2.

• Setup: 3->2->0->-4->2 (cycle at 2).
• Phase 1: Detect Cycle:
• slow = 3, fast = 3.
• slow = 2, fast = 0.
• slow = 0, fast = 2.
• slow = -4, fast = 0.
• slow = 2, fast = -4.
• slow = 0, fast = 2 (meet at 0).
• Phase 2: Find Entry:
• slow = 3, fast = 0.
• slow = 2, fast = -4.
• slow = 0, fast = 2 (meet at 2).
• Finish: Return Node 2.

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

Goal: Return Node 1.

• Setup: 1->2->1.
• Phase 1: slow = 1, fast = 1, slow = 2, fast = 1, slow = 1, fast = 1 (meet).
• Phase 2: slow = 1, fast = 1 (meet at 1).
• Finish: Return Node 1.

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

Goal: Return null.

• Setup: 1->null.
• Phase 1: slow = 1, fast = 1, fast = null, no meeting.
• Finish: Return null.

How the Code Works (Floyd’s Cycle Detection with Entry Point) – 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 detectCycle(head: ListNode) -> ListNode:
    # 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
        return None

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

    # Line 3: Phase 1 - Detect cycle
    while fast and fast.next:
        # Continue while fast can move (e.g., not null)
        slow = slow.next
        # Move one step (e.g., 3->2)
        fast = fast.next.next
        # Move two steps (e.g., 3->0)
        if slow == fast:
            # If they meet (e.g., at 0), cycle exists
            break
    else:
        # If fast reaches null (e.g., acyclic), no cycle
        return None

    # Line 4: Phase 2 - Find cycle entry
    slow = head
    # Reset slow to head (e.g., 3)
    while slow != fast:
        # Move both one step until they meet (e.g., at 2)
        slow = slow.next
        # e.g., 3->2
        fast = fast.next
        # e.g., 0->-4->2

    # Line 5: Return cycle entry node
    return slow
    # Node where cycle begins (e.g., 2)

This detailed breakdown clarifies how Floyd’s algorithm finds the cycle entry.

Alternative: Hash Set with Tracking Approach

Explanation

Hash Set with Tracking uses a set to store visited nodes, returning the first node revisited, which is the cycle entry. It’s a practical alternative, simple with O(n) time, but uses O(n) space, less optimal than Floyd’s for space constraints.

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

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

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 Node 2.
• Finish: Return Node 2.

How the Code Works (Hash Set)

Copy codedef detectCycleHash(head: ListNode) -> ListNode:
    visited = set()
    curr = head
    while curr:
        if curr in visited:
            return curr
        visited.add(curr)
        curr = curr.next
    return None

Complexity

• Floyd’s Cycle Detection with Entry Point:
• Time: O(n) – linear with meeting and entry finding.
• Space: O(1) – two pointers.
• Hash Set with Tracking:
• Time: O(n) – single pass.
• Space: O(n) – hash set.

Efficiency Notes

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

Key Insights

• Floyd’s: Detects and locates cycle entry.
• Hash Set: Tracks visited nodes.
• Cycle Entry: First revisited node.

Additional Example

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

• Goal: Node 3.
• Floyd’s: Meet in cycle, reset, meet at 3.

Edge Cases

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

Both solutions handle these well.

Final Thoughts

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