L14. Detect a Loop or Cycle in a Linked List | With Proof and Intuition

Detecting a loop or cycle in a singly linked list is a classic data structures and algorithms (DSA) problem. Given the head of a linked list, our goal is to return true if a cycle exists (i.e., you can traverse forward and eventually reach a node you have already visited) and false otherwise. This document explores the problem from a brute-force hashing approach to the optimal constant-space Tortoise and Hare algorithm, complete with mathematical intuition and code implementations.

1. What is a Loop in a Linked List?

A loop occurs when a node's next pointer does not terminate at null, but instead points back to a previously visited node in the sequence.

• Formal Definition: A linked list contains a loop if there exists a minimum of one node where you can start traversing forward and eventually reach back to that exact same node.
• Visual Example:
  Structure & Concept Flow

  Copy DiagramCopy

  1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

  ^ |

  |-----------------------------|

   
  In the example above, starting from node 3 and moving forward will eventually bring you back to 3. Therefore, a loop exists.

2. The Brute-Force Approach: Hashing Nodes

The Core Idea

To detect if a node has been visited more than once, we need to remember the nodes we encounter during traversal. When we visit a node that is already stored in our memory, we know a cycle exists.

Note: Always store the entire node object/memory reference, not its integer value. Linked lists can contain duplicate values across different nodes, so checking values alone will yield false positives.

Algorithm Steps

1. Initialize a temporary pointer temp pointing to the head of the linked list.
2. Initialize a Hash Map or Hash Set to store visited node references (e.g., Node* as keys in C++, or HashMap<Node, Integer> in Java).
3. Traverse the list node by node:
   • Before inserting temp into the map, check if it already exists.
   • If it exists, return true (cycle detected).
   • If it does not exist, insert temp into the map and advance temp = temp.next.
4. If temp reaches null, the traversal terminates, meaning the list is linear. Return false.

Pseudocode (Hashing Approach)

bool detectCycle(Node* head) {
    Node* temp = head;
    unordered_map<Node*, int> visitedMap;
    
    while (temp != nullptr) {
        if (visitedMap.find(temp) != visitedMap.end()) {
            return true; // Loop detected
        }
        visitedMap[temp] = 1;
        temp = temp->next;
    }
    return false; // Reached null, linear list
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$ where $N$ is the number of nodes, assuming hash map insertions and lookups take $\mathcal{O}(1)$ average time.
• Space Complexity: $\mathcal{O}(N)$ because in the worst case (a full cycle or a very long list), every node is stored in the hash map.

3. The Interview Challenge: Optimizing Space

While the hashing approach runs in linear time $\mathcal{O}(N)$, interviewers will typically push for an optimal space complexity of $\mathcal{O}(1)$.

To achieve this without using external data structures, we use the Tortoise and Hare Algorithm (also known as the Slow and Fast Pointer approach), which was previously used to find the middle of a linked list.

4. The Optimal Approach: Tortoise and Hare Algorithm

Core Mental Model

Imagine two runners on a circular running track:

• The Tortoise (Slow Pointer) moves at a speed of 1 step at a time.
• The Hare (Fast Pointer) moves at a speed of 2 steps at a time.

If the track is linear (straight line), the fast runner will eventually reach the end (null). However, if the track is circular (contains a loop), the fast runner will lap the slow runner, and both pointers will eventually collide at the exact same node.

Step-by-Step Flow Walkthrough (Cycle Present)

5. Handling Edge Cases: Linear Lists vs. Cyclic Lists

When implementing the slow and fast pointer approach, we must handle two distinct termination conditions:

1. Cyclic Linked List: The fast pointer will never hit null. Instead, slow == fast will evaluate to true, confirming a loop.
2. Linear Linked List (Odd or Even nodes): The fast pointer will eventually reach the end of the list (null).

Boundary Condition Check

Before advancing the fast pointer by two steps, we must verify that neither the current fast node nor its next node is null to prevent segmentation faults (NullPointerException):

while (fast != nullptr && fast->next != nullptr) {
    slow = slow->next;          // Moves 1 step
    fast = fast->next->next;    // Moves 2 steps
    
    if (slow == fast) {
        return true;            // Cycle detected
    }
}
return false;                   // Reached end of linear list

6. Mathematical Proof & Intuition: Why Do They Always Collide?

A common question is: What if the fast pointer jumps over the slow pointer and they never collide? Let's break down the mathematical proof of why a collision is guaranteed.

Distance Reduction Mechanics

1. Assume at some point during traversal, the slow pointer is at one position and the fast pointer is ahead of it.
2. Let the distance from the fast pointer to the slow pointer (measured by traversing forward along the loop) be $D$.
3. In each iteration:
   • The slow pointer moves forward by 1 step (increasing the gap from behind).
   • The fast pointer moves forward by 2 steps (closing the gap towards the slow pointer).
4. Net Reduction in Distance:

Because the distance $D$ reduces by exactly 1 unit with every single step, and $D$ is a finite integer, it is mathematically bound to decrease sequentially:

Once the distance reaches 0, the slow and fast pointers occupy the exact same memory address. They cannot jump over each other because the gap closes smoothly by 1 step at a time.

7. Complete Code Implementation

C++ Implementation

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        
        ListNode* slow = head;
        ListNode* fast = head;
        
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;          // 1 step
            fast = fast->next->next;    // 2 steps
            
            if (slow == fast) {
                return true;            // Collision -> Loop exists
            }
        }
        
        return false;                   // Reached null -> Linear list
    }
};

Java Implementation

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;           // 1 step
            fast = fast.next.next;      // 2 steps
            
            if (slow == fast) {
                return true;            // Collision -> Loop exists
            }
        }
        
        return false;                   // Reached null -> Linear list
    }
}

8. Summary Comparison Table

9. Summary and Key Takeaways

• Definition of a Loop: A linked list has a loop if at least one node can be visited more than once by traversing next pointers.
• Node References over Values: Always store and compare node object references in hash structures, as node values can repeat.
• Brute-Force Tradeoff: Hashing gives an intuitive $\mathcal{O}(N)$ time solution but incurs $\mathcal{O}(N)$ space overhead.
• Optimal Strategy: The Tortoise and Hare algorithm achieves $\mathcal{O}(N)$ time with strict $\mathcal{O}(1)$ auxiliary space.
• Pointer Speeds: The slow pointer moves at $1\times$ speed and the fast pointer moves at $2\times$ speed.
• Gap Reduction Proof: Because the fast pointer reduces the distance to the slow pointer by exactly 1 unit per step, they are mathematically guaranteed to collide without skipping over each other.
• Termination Safety: Always check fast != nullptr && fast->next != nullptr to avoid null pointer exceptions in linear lists.