Domain 2MediumCORE

Linked List Cycle II

We are given the head of a singly linked list and need to identify if there is a cycle within that structure. If one exists, we must return the specific node where the loop begins (the entry point). We also have an implicit constraint from the follow-up: we cannot modify the nodes' pointers or use extra memory proportional to $N$.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Linked List#Two Pointers

142. Linked List Cycle II

Model: qwen3.5:9b
Topics: Linked List,Two Pointers
FAANG asked: 1
Acceptance rate: 40.0%


Problem Breakdown

We are given the head of a singly linked list and need to identify if there is a cycle within that structure. If one exists, we must return the specific node where the loop begins (the entry point). We also have an implicit constraint from the follow-up: we cannot modify the nodes’ pointers or use extra memory proportional to NN.

Inputs:

  • head: The starting node of a linked list (ListNode object).

Outputs:

  • Returns the ListNode where the cycle starts.
  • Returns None if no cycle exists.

Edge Cases & Constraints:

  1. Empty List: If head is None, there can be no cycle. Return None.
  2. No Cycle: The fast pointer will eventually hit a null terminator before meeting the slow pointer. We must handle this gracefully to avoid returning an invalid node or crashing on attribute access (fast.next).
  3. Cycle at Head vs Tail: The logic should work regardless of where the cycle entry is relative to the head.
  4. Single Node: If a single node points to itself, that node is the start.

Intuition

A brute-force approach would be to traverse the list and store every visited node in a hash set (or array). Every time we visit a new node, we check if it’s already in our storage. If yes, we found the cycle entry. However, this uses O(N)O(N) space, which violates the follow-up constraint for constant memory usage.

To solve this with O(1)O(1) space, I recall Floyd’s Tortoise and Hare algorithm (Two Pointers). Phase 1: Detection. We use two pointers moving at different speeds—a slow pointer (slow) moves one step per iteration, while a fast pointer (fast) moves two steps. If there is no cycle, fast will eventually reach the end of the list (None). If there is a cycle, they are guaranteed to meet inside the loop because the faster runner laps the slower runner within the finite length of the circle.

Phase 2: Locating Entry. This is the mathematical insight required for O(1)O(1) space. Let μ\mu be the distance from head to the start of the cycle, and let LL be the cycle’s circumference. When they meet inside the loop at a specific point (let’s call it meeting node), suppose the slow pointer has traveled exactly μ+k\mu + k steps (k<Lk < L). The fast pointer travels twice that distance: 2(μ+k)2(\mu + k). The difference in their distances is (Fast)−(Slow)=μ+nL(\text{Fast}) - (\text{Slow}) = \mu + nL, where nn is the number of laps. Since Fast moves 1 extra step per iteration relative to Slow, they meet when fast has lapped exactly enough times such that: Distance(Head)=μ\text{Distance}(Head) = \mu.

If we reset one pointer back to head and keep the other at the meeting point, moving both forward by 1 node each time, they will collide again. The distance from head to entry is μ\mu, and the distance from the meeting point (inside loop) backwards along the cycle logic effectively aligns such that this collision happens exactly at the start of the cycle (μ\mu steps away).

Approach

  1. Initialize Pointers: Set slow and fast both to head.
  2. Detect Cycle: Move pointers in a loop: increment slow by 1, fast by 2. If either pointer becomes null (specifically checking fast.next before moving), break the loop—no cycle exists.
  3. Handle Collision: Once they meet inside the cycle, we know a cycle exists.
  4. Find Entry Point: Reset one pointer (ptr) to head. Keep the other at the meeting point. Move both pointers forward by exactly 1 step per iteration until they are equal again. The node where they converge is the start of the cycle.

Complexity Analysis

  • Time Complexity: O(N)O(N). We traverse the list twice in the worst case (once to detect, once to find entry). In a non-cyclic list, we stop early when fast hits null.
  • Space Complexity: O(1)O(1). We only use two pointers (slow, fast) and one auxiliary pointer for resetting. No hash sets or recursion stacks are used.

Solution

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

def detectCycle(head):
    # Handle empty list case immediately
    if not head:
        return None
    
    slow = fast = head
    
    # Phase 1: Detect cycle using Floyd's algorithm
    while True:
        # Check for termination (no cycle) before moving pointers. 
        # We must check both next to avoid AttributeError on null.next
        if not fast or not fast.next:
            return None
        
        slow = slow.next
        fast = fast.next.next
        
        # If they meet, a cycle exists
        if slow == fast:
            break
            
    # Phase 2: Find the start of the cycle
    # Reset one pointer to head. 
    # The distance from Head -> CycleStart equals Distance(MeetingNode) -> CycleStart (modulo L).
    ptr = head
    
    while ptr != slow:
        ptr = ptr.next
        slow = slow.next
        
    return ptr

# Example usage logic would be handled by the caller passing a ListNode object.

Edge Cases Handled

  • Empty List (head is None): The function returns None immediately at the start, preventing traversal errors.
  • No Cycle: If fast reaches the end of the list (either fast or fast.next becomes null), we return None. This prevents infinite loops in non-cyclic lists.
  • Cycle Starts at Head (pos = 0): The math holds; if μ=0\mu=0, both pointers meet immediately after entering, and resetting one to head results in immediate equality or convergence logic works correctly as distance is zero.
  • Single Node with Self Loop: slow moves to node A, fast moves to node A (2 steps wraps around). They collide at the single node. Resetting both starts them equal immediately? No, slow stays at collision, ptr resets to head (same node), loop condition ptr != slow is false initially if they are same object reference after reset logic check? Wait:
    • If cycle length 1 and μ=0\mu=0: Fast moves A->A. Slow moves A->A. They meet immediately in Phase 1.
    • Reset ptr to head (Node A). slow at Node A. ptr != slow is False. Returns Node A. Correct.
  • Cycle Starts Near Tail: The distance logic holds regardless of where the entry point lies relative to the tail connection index.