Linked List Cycle Detection #

Solution: Two Pointers Approach #

public static boolean hasCycle(ListNode head) {
    // Handle edge cases
    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 with different speeds
    while (fast != null && fast.next != null) {
        slow = slow.next;         // Move slow pointer 1 step
        fast = fast.next.next;    // Move fast pointer 2 steps

        // If pointers meet, there's a cycle
        if (slow == fast) {
            return true;
        }
    }

    // Fast pointer reached end (null), no cycle
    return false;
}

Algorithm Explanation: Two Pointers Technique #

Different Speed Strategy #

Note: This algorithm is also known as Floyd's Cycle Detection or the "Tortoise and Hare" algorithm.

This algorithm uses two pointers moving at different speeds:

• Slow pointer (tortoise): Moves 1 step at a time
• Fast pointer (hare): Moves 2 steps at a time

Key Insight #

If there's a cycle: The fast pointer will eventually "lap" the slow pointer and they will meet inside the cycle.

If there's no cycle: The fast pointer will reach the end (null) first.

Why This Works #

Mathematical Proof:

• If there's a cycle, both pointers will eventually enter it
• Once both are in the cycle, the fast pointer gains 1 position on the slow pointer each iteration
• Since the cycle is finite, the fast pointer will eventually catch up to the slow pointer

Visual Trace #

Example 1: Cycle exists

List: 3 -> 2 -> 0 -> -4
           ↑         |
           +---------+

Initial: slow = 3, fast = 3

Step 1: slow = 2, fast = 0
        slow moves 1 step (3 -> 2)
        fast moves 2 steps (3 -> 2 -> 0)

Step 2: slow = 0, fast = 2
        slow moves 1 step (2 -> 0)
        fast moves 2 steps (0 -> -4 -> 2)

Step 3: slow = -4, fast = -4
        slow moves 1 step (0 -> -4)
        fast moves 2 steps (2 -> 0 -> -4)

Step 4: slow == fast. They meet at node -4. → return true

Example 2: No cycle

List: 1 -> 2 -> 3 -> 4 -> 5 -> null

Initial: slow = 1, fast = 1

Step 1: slow = 2, fast = 3
Step 2: slow = 3, fast = 5
Step 3: slow = 4, fast = null (fast.next = null, can't move 2 steps)

Fast reached null → return false

Alternative Approaches (Less Efficient) #

Approach 1: Counting Steps (Not Recommended) #

This approach tries to detect cycles by limiting how many steps we take:

public static boolean hasCycleStepLimit(ListNode head) {
    ListNode current = head;
    int steps = 0;
    int maxSteps = 10000; // Arbitrary limit

    while (current != null && steps < maxSteps) {
        current = current.next;
        steps++;
    }

    // If we've taken too many steps, assume cycle
    return steps >= maxSteps;
}

Why it's not good:

• The step limit is just a guess - it might be too small or too large
• Not reliable for all cases
• Doesn't actually prove a cycle exists

Approach 2: Marking Visited Nodes (Not Recommended) #

This approach tries to mark nodes we've already seen:

public static boolean hasCycleDestructive(ListNode head) {
    ListNode current = head;
    final int VISITED_MARKER = Integer.MIN_VALUE;

    while (current != null) {
        if (current.val == VISITED_MARKER) {
            return true; // We've seen this node before
        }
        current.val = VISITED_MARKER; // Mark as visited
        current = current.next;
    }

    return false;
}

Why it's not good:

• Changes the original data (destructive)
• Fails if the marker value naturally exists in the list
• In real applications, you usually can't modify the input data

Performance Analysis #

Two Pointers Approach:

• Time Efficiency: Linear performance in the worst case
  • If no cycle: traverse entire list once (fast pointer moves through all nodes)
  • If cycle exists: at most 2n steps where n is the number of nodes
• Memory Efficiency: Very efficient memory usage
  • Only uses two pointer variables
  • No additional data structures needed
  • Perfect constant space usage

Key Insights #

This problem demonstrates:

• Two pointers technique with different movement speeds
• Cycle detection without additional memory
• Mathematical reasoning behind algorithm correctness
• Edge case handling (empty list, single node)
• Elegant problem solving using simple pointer manipulation

Common Mistakes #

1. Null pointer exceptions: Not checking if fast.next is null before moving
2. Wrong termination condition: Not handling the case where fast reaches null
3. Incorrect pointer initialization: Starting pointers at wrong positions
4. Missing edge cases: Not handling empty list or single node
5. Infinite loop: Not advancing pointers correctly

Edge Cases #

1. Empty list: head = null → return false
2. Single node, no cycle: [1] -> null → return false
3. Single node, self cycle: [1] -> [1] → return true
4. Two nodes, no cycle: [1,2] -> null → return false
5. Two nodes with cycle: [1,2] where 2 -> 1 → return true

Step-by-Step Execution #

Detailed trace for cycle detection:

List with cycle: A -> B -> C -> D
                      ↑         |
                      +---------+

Iteration  | Slow | Fast | Notes
-----------|------|------|------------------
Initial    |  A   |  A   | Both start at head
1          |  B   |  C   | slow+1, fast+2
2          |  C   |  D   | continuing...
3          |  D   |  C   | fast cycles back
4          |  C   |  D   | slow enters cycle
5          |  D   |  C   | both in cycle
6          |  C   |  D   | getting closer...
7          |  D   |  C   | very close...
8          |  C   |  C   | MEET! → return true

Key insight: Once both pointers are in the cycle,
the distance between them decreases by 1 each step
until they meet.