In software development, managing recursive data structures like linked lists requires careful pointer traversal. A common pitfall is the accidental creation of a cycle, or loop, where a node points back to an earlier element in the list. Left undetected, navigating such a list will result in infinite loops, CPU starvation, or stack overflows. The Detect Cycle in a Linked List problem challenges us to write an algorithm that detects these loops efficiently before they cause system errors.

For instance, consider a list 3 → 2 → 0 → -4, where the tail node -4 points back to node 2. A program scanning this list will iterate endlessly between 2, 0, and -4. Detecting this scenario is critical for memory safety and general runtime robustness.

Illustration of Floyd's Cycle Detection algorithm (Tortoise and Hare) in Java
Real-World Analogy: The Race Track

To understand loop detection, picture a classic race track containing two runners: a slow-moving Tortoise and a fast Hare:

  • If the track is a straight path with a defined finish line, the fast Hare will reach the end quickly and stop. The Tortoise will eventually follow.
  • However, if the track forms a loop, the Hare will run endlessly in circles. Because the Hare moves at twice the speed of the Tortoise, they will eventually enter the loop, close the distance, and lap the Tortoise, meeting at the exact same point on the track.
By checking if the two runners ever stand on the same spot, we can prove mathematically whether the track contains a loop or a straight finish.

Algorithmic Solutions

1. HashSet Visited Log (O(n) Time, O(n) Space)

We can traverse the linked list from the head, saving each node's memory address into a HashSet. Before moving to the next node, we check if the node is already present in the set. If it is, we've found a loop. While simple, storing these addresses consumes extra memory.

2. Floyd's Cycle Detection Algorithm (O(n) Time, O(1) Space)

Also known as the Tortoise and Hare algorithm, this approach uses two pointers initialized at the head:

  • slow: Advances by one node at a time (slow = slow.next).
  • fast: Advances by two nodes at a time (fast = fast.next.next).
If the fast pointer reaches null, the list has no loop. If a cycle exists, the fast pointer will catch up to the slow pointer inside the loop. The moment slow == fast, we return true.

Step-by-Step Scenario Trace

Let's trace Floyd's algorithm on the list 3 → 2 → 0 → -4 (where -4 loops back to 2):

  • Initialization: Both slow and fast pointers point to the head node (3).
  • Iteration 1: slow moves to 2. fast moves to 0. They are not equal, so we continue.
  • Iteration 2: slow moves to 0. fast moves two steps (from 0 to -4 and then back to 2). They are not equal, so we continue.
  • Iteration 3: slow moves to -4. fast moves two steps (from 2 to 0 and then to -4). Pointers meet!
Since slow == fast, the loop ends and we return true.

Key Code Explanations

Here is why the main logic in the solution is important:

  • while (fast != null && fast.next != null): Ensures we do not encounter a NullPointerException when checking the fast runner's future steps. If either is null, we reached the end of a straight list, meaning no cycle exists.
  • slow = slow.next; fast = fast.next.next;: Advances the pointers at different speeds, allowing the Hare to lap the Tortoise mathematically within a cycle.
  • if (slow == fast) return true;: The definitive meeting condition proving the cycle's existence.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;
 
public class DetectCycleLinkedList {
 
    public static class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int val) { this.val = val; }
    }
 
    // Optimized - Floyd's Cycle Detection - O(n)
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
 
    public static void main(String[] args) {
        DetectCycleLinkedList solver = new DetectCycleLinkedList();
        ListNode head = new ListNode(3);
        ListNode cycleNode = new ListNode(2);
        head.next = cycleNode;
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(-4);
        head.next.next.next.next = cycleNode; // Cycle created
 
        System.out.println("--- Detect Cycle in Linked List Demonstration ---");
        System.out.println("Floyd's Tortoise and Hare algorithm maps fast pointer and slow pointer.");
        System.out.println("Has Cycle: " + solver.hasCycle(head));
    }
}

Conclusion & Complexity Analysis

Floyd's Cycle Detection algorithm is a brilliant example of pointer optimization. It runs in O(N) linear time complexity and uses a constant O(1) space complexity. This makes it highly superior to the HashSet approach, which requires extra allocation. Mastering two-pointer strategies is essential for solving complex list-traversal problems.