Detecting Cycles in Linked Lists and Graphs

Cycle detection represents one of the most fundamental and frequently asked algorithmic problems in technical interviews, particularly when assessing candidates' understanding of linked list manipulation and graph traversal techniques.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Are we dealing with a linked list, array, or graph structure for cycle detection?
2. What is the expected input size and constraints (e.g., max array length, node count)?
3. Can we modify the input structure during our solution (e.g., mark visited nodes)?
4. Should we return the start node of the cycle or just a boolean indicating its presence?
5. What is the target time complexity for follow-up (e.g., O(n) or O(n log n))?

Restatement of the pattern: Cycle detection is a fundamental algorithmic pattern used to identify when a sequence, traversal, or structure contains a repeated element or path that loops back on itself. In the context of linked lists, it determines whether a node can be reached again by traversing from the head. In arrays or graphs, it identifies cycles in traversal paths.

Signal words and constraint shape:

• "Detect cycles" or "find loop"
• "Return the start of cycle"
• "Linked list with cycles"
• "Array where elements point to indices"
• "Graph traversal with repeated nodes"
• "Traversing a sequence that may loop"

Assumptions made:

• The input structure (linked list, array, graph) is well-formed and has a valid starting point
• For linked lists, each node has a next pointer that either points to another node or null
• The problem is asking for structural cycles, not value-based duplicates

Scenario suitability: This pattern is primarily suited for static input structures where we can traverse once or multiple times to detect cycles. It's less appropriate for streaming data where the cycle might not be fully visible yet, though it can be adapted for online scenarios with appropriate buffering or state tracking.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Cycle" or "loop" in the problem description
• "Return the node where the cycle begins"
• "Detect if a linked list has a cycle"
• "Find the start of the loop in a linked list"
• References to "fast and slow pointers" or "Floyd's cycle detection"
• Problems involving sequences that may revisit elements
• Graph problems with cycles in directed or undirected structures

Why this pattern fits better than the most common alternatives: The cycle detection pattern uses Floyd's Cycle Detection Algorithm (tortoise and hare) which provides optimal O(1) space complexity compared to hash-based approaches that require O(n) extra space. It's specifically designed for detecting cycles in sequences or linked structures and leverages mathematical properties of cycle geometry to find the start point efficiently.

Conditions where a variation or related pattern applies instead:

• For undirected graphs, use Union-Find or DFS with visited tracking to detect cycles
• For topological sorting problems, use Kahn's algorithm or DFS-based cycle detection
• For finding the start of a cycle in arrays, use similar Floyd's approach but adapted for array indexing
• For detecting cycles in graphs with edge weights, use Bellman-Ford or DFS with color marking

The core insight that makes this pattern work: The mathematical property that when a slow pointer moves 1 step and a fast pointer moves 2 steps, they will meet inside the cycle if one exists. Then, by resetting one pointer to the head and moving both at same speed, they will meet at the cycle's starting node. This is based on the fact that the distance from head to cycle start equals the distance from meeting point to cycle start along the cycle.

3. Approach Evolution

Interview communication script:

My first instinct is to use a brute force approach where I traverse the linked list and store visited nodes in a HashSet, checking if I've seen a node before. But that's O(n²) time complexity in worst case because for each node I might have to scan the entire set of previously seen nodes, and it's also O(n) space for storing all visited nodes.

Let me think about how to optimize this. I notice that if I use the Floyd's Cycle Detection algorithm with two pointers - a slow pointer moving one step at a time and a fast pointer moving two steps at a time - I can detect cycles without needing extra space.

The key insight is that if there's a cycle, the fast pointer will eventually "lap" the slow pointer inside the cycle. If there's no cycle, the fast pointer will reach the end of the list first.

I'm going to use Floyd's Cycle Detection algorithm because:

1. It's O(1) space complexity - no extra data structures needed
2. It's O(n) time complexity - we visit each node at most twice
3. The mathematical property that if there's a cycle, the two pointers will meet proves correctness

Let me walk through the logic: if we have a cycle of length C, and the slow pointer is at position S and fast pointer at position F in the cycle, then when they meet, we can prove that the distance from head to cycle start equals the distance from meeting point back to cycle start.

The important invariant that must hold is: fast pointer moves twice as fast as slow pointer, and they both move forward one step at a time (or null if at end). When fast pointer reaches the end of list, we know there's no cycle.

Brute-force approach:

• Store visited nodes in a HashSet
• For each node, check if already seen
• Time: O(n²) worst case (nested iteration), Space: O(n)
• Not ideal due to quadratic time complexity and linear space usage

Improved approach - Floyd's Cycle Detection:

• Use two pointers moving at different speeds
• Fast pointer moves 2 steps, slow pointer moves 1 step
• If there's a cycle, they will eventually meet
• Time: O(n), Space: O(1)
• Optimal solution for cycle detection in linked lists

Final approach with step-by-step reasoning:

1. Initialize two pointers at head
2. Move slow pointer one step, fast pointer two steps
3. If fast pointer reaches null, no cycle exists
4. If pointers meet, cycle detected
5. This works because in a cycle, the fast pointer will eventually "lap" the slow one

Key invariant: Fast pointer is always moving twice as fast as slow pointer, and they both advance until one reaches the end or they meet.

4. Data Structure Choice

For cycle detection in a linked list, the primary data structures are:

Linked List Node Structure:

• The input structure itself - a singly linked list where each node has a val field and a next pointer
• This is the fundamental data structure we're operating on

HashSet for Cycle Detection:

• Used in the hash set approach to store visited nodes
• Provides O(1) average lookup time to detect if we've seen a node before
• Space complexity of O(n) in worst case

Two Pointers (Slow/Fast):

• In the optimal Floyd's Cycle Detection approach, we use only two pointers (typically called slow and fast)
• No additional data structures required beyond these two references
• Space complexity of O(1)

Why Each Choice Works:

• The HashSet approach is intuitive and easy to understand, but uses extra space
• Floyd's algorithm is optimal in both time and space complexity
• The two-pointer technique works because if there's a cycle, the fast pointer will eventually "lap" the slow pointer
• We don't need any additional collections or complex data structures - just the input structure and a few references

Trade-offs:

• HashSet approach is more readable but uses O(n) space
• Two-pointer approach is optimal in both time and space but requires more conceptual understanding of the mathematical properties of cycles

The two-pointer approach is preferred for cycle detection because it's space-efficient and leverages the mathematical property that in a cyclic structure, a fast-moving pointer will eventually catch up to a slower one.

5. Algorithm Walkthrough

Let me trace through the Floyd's Cycle Detection algorithm on a concrete example to show how it works.

Example: [3, 2, 0, -4] with tail connecting to index 1 (value 2)

Step-by-step execution:

1. Initialization:

   • slow = 0, fast = 0
   • Both pointers start at index 0 (value 3)

2. First iteration:

   • Move slow: slow = nums[0] = 3
   • Move fast: fast = nums[nums[0]] = nums[3] = -4
   • Now slow points to index 3, fast points to index 3

3. Second iteration:

   • Move slow: slow = nums[3] = -4
   • Move fast: fast = nums[nums[-4]] → This would be out of bounds!

Wait, let me reconsider the example structure. Let me use a proper cycle detection example:

Revised Example: [1, 3, 2, 4, 5] where index 1 points to index 3 (value 4), and index 3 points back to index 1, creating a cycle.

Actually, let me properly construct the problem: We have array nums where each element points to another index. Let's say we have [1, 2, 3, 4, 5] with index 1 pointing to index 2, index 2 to index 3, etc., but we'll make a cycle by having index 4 point back to index 1.

Better example: [1, 2, 3, 4, 1] where index 0 → 1, index 1 → 2, index 2 → 3, index 3 → 4, index 4 → 1 (cycle)

Step-by-step execution:

1. Initialization:

   • slow = 0, fast = 0
   • Both start at index 0 (value 1)

2. First iteration:

   • Move slow: slow = nums[0] = 1
   • Move fast: fast = nums[nums[0]] = nums[1] = 2
   • Now slow points to index 1, fast points to index 2

3. Second iteration:

   • Move slow: slow = nums[1] = 2
   • Move fast: fast = nums[nums[2]] = nums[3] = 4
   • Now slow points to index 2, fast points to index 4

4. Third iteration:

   • Move slow: slow = nums[2] = 3
   • Move fast: fast = nums[nums[4]] = nums[1] = 2
   • Now slow points to index 3, fast points to index 2

5. Fourth iteration:

   • Move slow: slow = nums[3] = 4
   • Move fast: fast = nums[nums[2]] = nums[3] = 4
   • Now slow points to index 4, fast points to index 4

6. Fifth iteration:

   • Move slow: slow = nums[4] = 1
   • Move fast: fast = nums[nums[4]] = nums[1] = 2
   • Now slow points to index 1, fast points to index 2

7. Sixth iteration:

   • Move slow: slow = nums[1] = 2
   • Move fast: fast = nums[nums[2]] = nums[3] = 4
   • Now slow points to index 2, fast points to index 4

8. Seventh iteration:

   • Move slow: slow = nums[2] = 3
   • Move fast: fast = nums[nums[4]] = nums[1] = 2
   • Now slow points to index 3, fast points to index 2

9. Eighth iteration:

   • Move slow: slow = nums[3] = 4
   • Move fast: fast = nums[nums[2]] = nums[3] = 4
   • Now slow points to index 4, fast points to index 4

At this point, slow == fast, so we've detected a cycle and return true.

Edge case handling:

• If array has only one element, we immediately detect no cycle (since there's no valid pointer to follow)
• If array has two elements and they form a self-loop, we detect it quickly
• The algorithm correctly handles arrays with negative numbers by treating them as valid indices (though in practice, we'd need to validate that indices are within bounds)

The algorithm terminates correctly because if there's a cycle, the fast pointer will eventually "lap" the slow pointer inside the cycle, and they'll meet at some point. If there's no cycle, the fast pointer will reach the end of the array first.

6. Java Solution

/**
 * Detects if a linked list has a cycle using Floyd's Cycle Detection Algorithm.
 * Uses two pointers moving at different speeds to detect cycles in O(1) space.
 */
public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    /**
     * Determines whether the given linked list contains a cycle.
     * 
     * @param head the head node of the linked list
     * @return true if there is a cycle, false otherwise
     */
    public boolean hasCycle(ListNode head) {
        // Handle edge cases: empty list or single node
        if (head == null || head.next == null) {
            return false;
        }
        
        // Initialize two pointers
        ListNode slow = head;      // moves 1 step at a time
        ListNode fast = head;      // moves 2 steps at a time
        
        // Traverse the list
        while (fast != null && fast.next != null) {
            slow = slow.next;          // Move slow pointer one step
            fast = fast.next.next;     // Move fast pointer two steps
            
            // If pointers meet, there's a cycle
            if (slow == fast) {
                return true;
            }
        }
        
        // If we reach here, no cycle was found
        return false;
    }
}

The solution implements Floyd's Cycle Detection Algorithm (also known as the "tortoise and hare" algorithm). It uses two pointers moving at different speeds through the linked list. If there's a cycle, the faster pointer will eventually "lap" the slower one and they'll meet. If there's no cycle, the faster pointer will reach the end of the list. This approach uses O(1) space and O(n) time complexity, making it optimal for this problem.

7. Complexity Analysis

Time Complexity: O(n) where n is the number of nodes in the linked list. The algorithm uses Floyd's Cycle Detection with two pointers moving at different speeds. In the worst case, both pointers traverse the list once - the fast pointer moves 2 steps each time while the slow pointer moves 1 step, but they both visit each node at most once. Even in the case where a cycle exists, the fast pointer will eventually catch up to the slow pointer within a finite number of steps, ensuring linear time complexity.

Space Complexity: O(1) - The algorithm only uses a constant amount of extra space regardless of input size. It maintains just two pointers (slow and fast) to traverse the list, with no additional data structures that grow with input size. This makes it optimal for space usage among cycle detection algorithms.

The bounds are correct because:

1. The fast pointer moves at 2x speed, so it will never skip over the slow pointer
2. If there's a cycle, the fast pointer will eventually "lap" the slow pointer inside the cycle
3. The number of steps required to detect a cycle is bounded by the length of the list
4. No additional memory allocation occurs beyond the two pointer variables

This solution is optimal for both time and space complexity, achieving linear time with constant space - the best possible trade-off for this problem. The solution is near-optimal because any algorithm that detects cycles in a linked list must examine at least some nodes to make the determination, and this approach achieves that minimum examination requirement efficiently.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty list: Handle null or empty input gracefully to avoid null pointer exceptions
• Single node: A list with one node that points to null should return false
• Self-loop: A single node pointing to itself should return true

Duplicate Values and Repeated States

• Lists with duplicate values don't change the cycle detection logic, but can make debugging harder
• The algorithm must detect cycles based on structural relationships, not node values

Boundary Conditions

• Null head: Must handle when the input list is null
• Valid cycle at end: A cycle where the last node points to a previous node (not necessarily head)
• Large input size: With 10^4 nodes, ensure the algorithm doesn't cause stack overflow or memory issues

Common Implementation Mistakes

• Not advancing pointers correctly: In Floyd's cycle detection, failing to advance slow pointer by one step while fast advances by two steps leads to incorrect results
• Missing null checks: Not checking if fast.next is null before accessing fast.next.next
• Incorrect termination condition: Using wrong loop conditions that cause infinite loops or premature exits
• Modifying input structure: Some approaches incorrectly modify the list structure (e.g., marking visited nodes), which violates problem constraints

// Example of incorrect null check:
// if (fast.next.next != null) { ... } // This is wrong - should check fast.next first
// Correct approach:
// if (fast.next == null || fast.next.next == null) return false;

9. Alternative Approaches

There are several alternative approaches to cycle detection, each with different trade-offs:

1. Hash Set Approach (Space-Optimal for Detection): Instead of Floyd's cycle detection, we can use a HashSet to track visited nodes. This approach has O(n) time and O(n) space complexity. It's simpler to understand but uses more memory than Floyd's algorithm.

public boolean hasCycle(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    ListNode current = head;
    
    while (current != null) {
        if (visited.contains(current)) {
            return true;
        }
        visited.add(current);
        current = current.next;
    }
    
    return false;
}

2. Two-Pointer with Different Speeds (Floyd's Algorithm Variants): We can use different step sizes for the slow and fast pointers, such as slow moving 1 step and fast moving 2 steps (standard Floyd), or even 1 and 3 steps. The standard 1:2 ratio is preferred for optimal performance.

3. Modifying Node Values (Not Recommended): We could mark visited nodes by changing their values to a special marker (e.g., Integer.MAX_VALUE). This approach modifies the input structure and is not suitable when input immutability is required.

4. Using Stack for Path Tracking: Store nodes in a stack as we traverse, checking if we revisit a node. This uses O(n) space and is less efficient than Floyd's algorithm for cycle detection.

The chosen solution (Floyd's Cycle Detection) is preferred because it provides O(1) space complexity while maintaining O(n) time complexity, making it optimal for memory-constrained environments. The hash set approach is simpler to understand but uses more space, while the stack-based approach adds unnecessary complexity for cycle detection specifically.

10. Test Cases

public class CycleDetectionTests {
    
    // Test case 1: Basic cycle detection
    @Test
    public void testBasicCycle() {
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2; // Creates cycle
        
        assertTrue(hasCycle(head));
    }
    
    // Test case 2: No cycle
    @Test
    public void testNoCycle() {
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        
        head.next = node2;
        node2.next = node3;
        node3.next = null; // No cycle
        
        assertFalse(hasCycle(head));
    }
    
    // Test case 3: Single node with self loop
    @Test
    public void testSingleNodeCycle() {
        ListNode head = new ListNode(1);
        head.next = head; // Self loop
        
        assertTrue(hasCycle(head));
    }
    
    // Test case 4: Empty list
    @Test
    public void testEmptyList() {
        assertNull(hasCycle(null));
    }
    
    // Test case 5: Two node cycle
    @Test
    public void testTwoNodeCycle() {
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        
        head.next = node2;
        node2.next = head; // Creates cycle
        
        assertTrue(hasCycle(head));
    }
    
    // Test case 6: Cycle at beginning
    @Test
    public void testCycleAtBeginning() {
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = head; // Cycle starts at head
        
        assertTrue(hasCycle(head));
    }
}

The test cases cover:

1. Basic cycle detection - A standard cycle in the middle of a list
2. No cycle scenario - Properly identifies when no cycle exists
3. Self-loop case - Edge case with single node pointing to itself
4. Empty list - Handles null input gracefully
5. Two-node cycle - Minimal cycle case
6. Cycle at beginning - When the cycle starts from the first node

Each test case validates different aspects of cycle detection including edge conditions, boundary cases, and various cycle configurations that could occur in real-world usage.

11. Final Summary

The core idea is to detect cycles in a linked list using the Floyd's Tortoise and Hare algorithm with two pointers moving at different speeds. When a cycle exists, the fast pointer will eventually "lap" the slow pointer, proving the existence of a loop. This solution is optimal because it uses O(1) space and O(n) time, making it ideal for production systems where memory constraints are critical. The elegance of this approach lies in its mathematical guarantee that if a cycle exists, the two pointers must meet within a finite number of steps, making it both theoretically sound and practically efficient for real-world applications.