LeetCode 142 - Linked List Cycle II

This problem asks us to determine whether a singly linked list contains a cycle and, if it does, return the exact node where that cycle begins. A linked list is normally a sequence of nodes where each node points to the next one, eventually ending with null.

leetcodemediumhash-tablelinked-listtwo-pointers

LeetCode Problem 142

Difficulty: 🟡 Medium
Topics: Hash Table, Linked List, Two Pointers

Solution

Problem Understanding

This problem asks us to determine whether a singly linked list contains a cycle and, if it does, return the exact node where that cycle begins.

A linked list is normally a sequence of nodes where each node points to the next one, eventually ending with null. However, in this problem, the next pointer of some node may point back to an earlier node instead of ending. When this happens, traversing the list repeatedly would cause us to revisit nodes forever, creating a cycle.

The input consists of the head node of a singly linked list. Internally, LeetCode provides a variable called pos, which indicates where the tail connects back into the list. However, this value is only used for constructing test cases and is not available to our algorithm. We must determine the cycle purely by traversing the linked list structure.

The expected output is the node object itself where the cycle begins. If there is no cycle, we return null (or None in Python). This distinction is important because we are not returning an index or node value, but the actual linked list node reference.

The constraints indicate that the linked list contains at most 10^4 nodes. This is small enough for an O(n) traversal to be efficient. The follow-up question asks for O(1) extra memory, which strongly suggests that solutions using auxiliary storage, such as a hash set, are not optimal.

Several edge cases are important to consider upfront. The linked list may be empty (head = null), meaning there cannot be a cycle. The list may contain only one node, either pointing to itself or ending normally. The cycle could begin at the head itself, which means returning the first node. The cycle might also begin deep in the list after several non-cyclic nodes. A naive implementation that only checks for repeated values instead of repeated node references would fail because multiple nodes can have identical values.

Approaches

Brute Force Approach, Hash Set

A straightforward way to solve this problem is to traverse the linked list while keeping track of every node we have already visited using a hash set.

As we move through the list, we check whether the current node has already been seen. If it has, then we know we have looped back into a cycle, and the current node must be the cycle entry point. If we eventually reach null, then no cycle exists.

This approach works because each node in a valid non-cyclic traversal should be visited exactly once. Revisiting a node means we have encountered a loop.

Although correct, this solution uses extra memory proportional to the number of nodes visited. Since the follow-up explicitly asks for constant extra memory, we can do better.

Optimal Approach, Floyd's Cycle Detection Algorithm

The key insight is that we can exploit pointer movement speeds to detect cycles without extra memory.

We use two pointers:

  • A slow pointer that moves one step at a time.
  • A fast pointer that moves two steps at a time.

If no cycle exists, the fast pointer will eventually reach null. If a cycle exists, the fast pointer will eventually "lap" the slow pointer inside the cycle, causing them to meet.

The deeper insight is how to find the entry point of the cycle after this meeting occurs.

Suppose:

  • L is the distance from the head to the cycle entry.
  • C is the cycle length.
  • X is the distance from the cycle entry to the meeting point.

At the meeting point:

  • Slow pointer distance = L + X
  • Fast pointer distance = L + X + kC

Since the fast pointer moves twice as fast:

$$2(L + X) = L + X + kC$$

Rearranging:

$$L + X = kC$$

Which implies:

$$L = kC - X$$

This means the distance from the head to the cycle entry equals the distance from the meeting point to the cycle entry.

Therefore, if we place one pointer back at the head and keep another at the meeting point, moving both one step at a time, they will meet exactly at the cycle entry node.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Uses a hash set to track visited nodes
Optimal O(n) O(1) Uses Floyd's two-pointer technique

Algorithm Walkthrough

  1. Initialize two pointers, slow and fast, both starting at head. The slow pointer will move one node at a time, while the fast pointer moves two nodes at a time.
  2. Traverse the linked list while ensuring the fast pointer and fast.next are not null. This check prevents invalid pointer access and also tells us whether the list ends normally.
  3. Move the pointers:
  • slow = slow.next
  • fast = fast.next.next

If there is no cycle, the fast pointer eventually reaches null. 4. After each movement, check whether slow == fast. If they meet, a cycle exists. This meeting point is guaranteed by Floyd's Cycle Detection Algorithm. 5. Once the pointers meet, initialize another pointer, cycle_start, at head. 6. Move both slow and cycle_start one step at a time:

  • slow = slow.next
  • cycle_start = cycle_start.next
  1. The node where these two pointers meet is the start of the cycle. Return that node.
  2. If the loop ends without the pointers meeting, return null because no cycle exists.

Why it works

The correctness comes from the mathematical relationship between the meeting point and the cycle entry. When the slow and fast pointers meet, the slow pointer has traveled a distance that aligns perfectly with the remaining distance to the cycle start. Resetting one pointer to the head ensures both pointers move the same remaining distance, causing them to meet exactly at the cycle entry node.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

from typing import Optional

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head

        # Step 1: Detect if a cycle exists
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                # Step 2: Find the cycle entry point
                cycle_start = head

                while cycle_start != slow:
                    cycle_start = cycle_start.next
                    slow = slow.next

                return cycle_start

        return None

The implementation begins by initializing both slow and fast pointers at the head of the linked list. The while fast and fast.next condition ensures safe pointer movement because the fast pointer advances two steps at a time.

Inside the loop, the slow pointer advances one node while the fast pointer advances two. If the list contains a cycle, the fast pointer eventually catches the slow pointer, proving a loop exists.

After detecting a meeting point, the algorithm creates a new pointer called cycle_start positioned at the head. Both cycle_start and slow then move one step at a time. Their meeting point is mathematically guaranteed to be the cycle entry node, which we return immediately.

If the loop exits naturally, the fast pointer reached the end of the list, meaning there is no cycle, so the function returns None.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    slow := head
    fast := head

    // Step 1: Detect cycle
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next

        if slow == fast {
            // Step 2: Find cycle entry
            cycleStart := head

            for cycleStart != slow {
                cycleStart = cycleStart.Next
                slow = slow.Next
            }

            return cycleStart
        }
    }

    return nil
}

The Go implementation follows the same logic as the Python version. The main difference is handling nil explicitly instead of None. Since Go pointers are strongly typed, we check fast != nil && fast.Next != nil before moving the fast pointer.

Go compares linked list nodes using pointer equality, which is exactly what we want because the problem requires identifying the same node object, not merely matching values.

There are no concerns about integer overflow because we are only moving pointers and not performing arithmetic on node values.

Worked Examples

Example 1

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

The structure is:

3 → 2 → 0 → -4
    ↑       ↓
    └───────┘

Cycle Detection Phase

Iteration Slow Fast
Start 3 3
1 2 0
2 0 2
3 -4 -4

The pointers meet at node -4.

Find Cycle Start

Reset cycle_start = head.

Step cycle_start slow
Start 3 -4
1 2 2

They meet at node 2, which is the cycle entry.

Example 2

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

Structure:

1 → 2
↑   ↓
└───┘

Cycle Detection Phase

Iteration Slow Fast
Start 1 1
1 2 1
2 1 1

Pointers meet at node 1.

Find Cycle Start

Step cycle_start slow
Start 1 1

They already match, so node 1 is returned.

Example 3

Input: head = [1], pos = -1

Structure:

1 → null

Cycle Detection Phase

Iteration Slow Fast
Start 1 1

Since fast.next is null, the loop ends immediately.

Result: return null.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each pointer traverses the list at most a constant number of times
Space O(1) Only a few pointer variables are used

The time complexity is O(n) because, even though there are two phases, each pointer moves through the linked list a bounded number of times. In the cycle detection phase, the pointers move until they meet or the list ends. In the second phase, both pointers move toward the cycle entry. Altogether, this remains linear in the number of nodes.

The space complexity is O(1) because we only store a constant number of pointer references regardless of input size.

Test Cases

# Definition for testing
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def detectCycle(self, head):
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                cycle_start = head

                while cycle_start != slow:
                    cycle_start = cycle_start.next
                    slow = slow.next

                return cycle_start

        return None

def build_cycle_list(values, pos):
    if not values:
        return None

    nodes = [ListNode(v) for v in values]

    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]

    if pos != -1:
        nodes[-1].next = nodes[pos]

    return nodes[0], nodes

solution = Solution()

# Example 1
head, nodes = build_cycle_list([3, 2, 0, -4], 1)
assert solution.detectCycle(head) == nodes[1]  # cycle starts at node value 2

# Example 2
head, nodes = build_cycle_list([1, 2], 0)
assert solution.detectCycle(head) == nodes[0]  # cycle starts at head

# Example 3
head, _ = build_cycle_list([1], -1)
assert solution.detectCycle(head) is None  # no cycle

# Empty list
assert solution.detectCycle(None) is None  # empty linked list

# Single node with self-cycle
head, nodes = build_cycle_list([1], 0)
assert solution.detectCycle(head) == nodes[0]  # node points to itself

# Long list with cycle in middle
head, nodes = build_cycle_list([1, 2, 3, 4, 5, 6], 2)
assert solution.detectCycle(head) == nodes[2]  # cycle starts at node value 3

# Two-node list without cycle
head, _ = build_cycle_list([1, 2], -1)
assert solution.detectCycle(head) is None  # normal termination

# Cycle at last node to itself
head, nodes = build_cycle_list([1, 2, 3], 2)
assert solution.detectCycle(head) == nodes[2]  # self-loop at tail
Test Why
[3,2,0,-4], pos=1 Validates a standard cycle beginning in the middle
[1,2], pos=0 Verifies cycle begins at head
[1], pos=-1 Ensures no cycle is detected
Empty list Confirms null input handling
Single node self-cycle Tests smallest possible cycle
Long list with middle cycle Validates cycle detection after long traversal
Two-node no cycle Ensures correct termination
Tail self-loop Confirms cycle entry can be the final node

Edge Cases

Empty Linked List

The input may be head = null. This is an easy case to overlook because dereferencing fast.next would immediately cause an error if not handled carefully. The implementation safely handles this through the loop condition while fast and fast.next, which fails immediately and returns None.

Single Node With Self-Cycle

A linked list with one node pointing to itself is a special but valid cycle. Some implementations mistakenly assume at least two nodes are needed for cycle detection. In this implementation, both pointers eventually meet on the same node, and resetting the second pointer correctly identifies that node as the cycle entry.

Cycle Starts at the Head

The cycle entry may be the very first node. This can break implementations that incorrectly assume there is always a non-cyclic prefix before the cycle. Floyd's algorithm naturally handles this case because, after the meeting point, the reset pointer and slow pointer will meet directly at the head.

No Cycle Exists

The linked list may terminate normally. A buggy implementation might loop forever if it assumes a cycle exists. Here, the fast pointer eventually becomes null, causing the loop to stop safely and return None.

Duplicate Node Values

Multiple nodes may contain identical values. A flawed approach might compare node values instead of node references, producing false positives. This implementation compares node objects directly, ensuring correctness even when values repeat.