Problem Description

You are given the head of a linked list. Your task is to determine whether the linked list contains a cycle.

A cycle exists in a linked list when a node can be reached again by continuously following the next pointers. In other words, if you keep traversing the list by moving from one node to the next, and you eventually arrive at a node you've already visited, then the list has a cycle.

The problem uses an internal variable pos to denote which node the tail connects back to (creating the cycle), but this variable is not provided as input to your function. You only receive the head of the linked list.

Your function should return true if a cycle exists anywhere in the linked list, and false if the linked list has no cycle (meaning it eventually terminates with a node pointing to null).

The solution uses a hash table approach where each node is stored in a set as we traverse the list. If we encounter a node that already exists in our set, we've found a cycle and return true. If we reach the end of the list (a null pointer) without finding any repeated nodes, we return false.

Intuition

When traversing a linked list, if there's no cycle, we'll eventually reach the end (a null pointer). However, if there's a cycle, we'll keep going around in circles forever, visiting the same nodes repeatedly.

The key insight is that in a cycle, we must revisit at least one node. Think of it like walking through rooms in a building - if there's no cycle, you'll eventually reach an exit. But if there's a cycle, you'll find yourself back in a room you've already been in.

To detect when we've entered a room we've seen before, we need to keep track of all the rooms (nodes) we've visited. A hash table (or set) is perfect for this because it allows us to quickly check if we've seen a node before in O(1) time.

As we traverse the linked list:

• We check if the current node is already in our set
• If it is, we've found our cycle - we're revisiting a node
• If it's not, we add it to our set and continue
• If we reach null, there's no cycle

This approach works because each node object in memory has a unique identity. When we store nodes in the set, we're storing references to these specific objects, not their values. So even if two nodes have the same value, they're different objects and won't create a false positive for cycle detection.

Solution Approach

The solution implements the hash table approach to detect cycles in a linked list. Here's how the implementation works:

Data Structure Used: A set s to store visited nodes.

Algorithm Steps:

1. Initialize an empty set s to keep track of all nodes we've visited.

2. Traverse the linked list using a while loop that continues as long as head is not None:

   while head:

3. Check for cycle at each node:

   • Before processing the current node, check if it already exists in our set:

     if head in s:
         return True

   • If the node is in the set, we've detected a cycle and immediately return True.

4. Mark the node as visited by adding it to the set:

   s.add(head)

5. Move to the next node in the linked list:

   head = head.next

6. Return False if no cycle found: If the loop completes (we reached a None pointer), the linked list has no cycle:

   return False

Time Complexity: O(n) where n is the number of nodes in the linked list. In the worst case, we visit all nodes once.

Space Complexity: O(n) for storing up to n nodes in the hash set.

The beauty of this approach is its simplicity - we're essentially keeping a "guest book" of all nodes we've visited. If we ever see a node trying to "sign in" twice, we know we've found a cycle.

Example Walkthrough

Let's walk through a small example to illustrate how the hash table approach detects a cycle.

Example: Linked list with a cycle

Consider this linked list: 1 -> 2 -> 3 -> 4 -> 2 (cycles back)

Where node 4's next pointer points back to the node with value 2, creating a cycle.

Step-by-step execution:

1. Start at head (node 1)

   • Set s = {}
   • Is node 1 in s? No
   • Add node 1 to set: s = {node1}
   • Move to head.next (node 2)

2. At node 2

   • Is node 2 in s? No
   • Add node 2 to set: s = {node1, node2}
   • Move to head.next (node 3)

3. At node 3

   • Is node 3 in s? No
   • Add node 3 to set: s = {node1, node2, node3}
   • Move to head.next (node 4)

4. At node 4

   • Is node 4 in s? No
   • Add node 4 to set: s = {node1, node2, node3, node4}
   • Move to head.next (back to node 2)

5. Back at node 2

   • Is node 2 in s? Yes! (we added it in step 2)
   • Return True - cycle detected!

Counter-example: Linked list without a cycle

Consider: 1 -> 2 -> 3 -> None

Following the same process:

• Visit node 1, add to set
• Visit node 2, add to set
• Visit node 3, add to set
• Move to head.next which is None
• Exit while loop
• Return False - no cycle found

The key insight is that we're storing actual node objects (memory references), not values. So even if two nodes have the same value, they're different objects in memory and won't trigger a false positive.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm traverses the linked list once using a while loop. In the worst case (when there is no cycle), it visits all n nodes exactly once. When there is a cycle, it visits at most n nodes before detecting a repeated node. Each operation inside the loop (checking membership in the set, adding to the set, and moving to the next node) takes O(1) average time for hash set operations. Therefore, the overall time complexity is O(n).

Space Complexity: O(n)

The algorithm uses a hash set s to store visited nodes. In the worst case (when there is no cycle), the set will contain all n nodes of the linked list. Even when there is a cycle, the set could potentially store up to n nodes before detecting the cycle. Therefore, the space complexity is O(n).

Common Pitfalls

1. Attempting to Use Node Values Instead of Node Objects

A common mistake is trying to detect cycles by storing node values in the set rather than the node objects themselves:

# INCORRECT approach
def hasCycle(self, head: Optional[ListNode]) -> bool:
    visited_values = set()
    current = head
    while current:
        if current.val in visited_values:  # Wrong! Checking values
            return True
        visited_values.add(current.val)
        current = current.next
    return False

Why this fails: Multiple nodes can have the same value without forming a cycle. For example, a list like 1 -> 2 -> 3 -> 2 -> 4 -> NULL has duplicate values but no cycle.

Solution: Always store the actual node objects (memory references) in the set, not their values:

if current in visited_nodes:  # Correct - checking node object
    return True
visited_nodes.add(current)     # Correct - storing node object

2. Memory Concerns with Large Lists

While the hash table approach is straightforward, it uses O(n) extra space. For very large linked lists, this could cause memory issues.

Alternative Solution: Use Floyd's Cycle Detection Algorithm (Tortoise and Hare) for O(1) space complexity:

def hasCycle(self, head: Optional[ListNode]) -> bool:
    if not head or not head.next:
        return False
  
    slow = head
    fast = head.next
  
    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next
  
    return True

3. Modifying the Original List Structure

Some might be tempted to mark visited nodes by modifying them (e.g., setting a special value or adding a visited flag), which alters the original data structure:

# INCORRECT - modifies the original list
def hasCycle(self, head: Optional[ListNode]) -> bool:
    current = head
    while current:
        if hasattr(current, 'visited'):  # Bad practice
            return True
        current.visited = True  # Modifying original node
        current = current.next
    return False

Why this is problematic:

• Violates the principle of not modifying input data
• May cause issues if the list is used elsewhere
• Not thread-safe

Solution: Stick with the hash set approach or Floyd's algorithm, both of which leave the original list intact.