Understanding Detect Cycle in Linked List in Java

Introduction & Problem Explanation

The Detect Cycle in a Linked List problem asks us to determine if a given linked list contains a cycle. A cycle exists if there is some node in the list that can be reached again by continuously following the next pointer.

For example, if the list is 3 -> 2 -> 0 -> -4 where -4 points back to 2, a cycle exists. If it terminates at null, there is no cycle. Reaching the end of a list without infinite loops is critical for memory safety and pointer traversal.

The Algorithmic Approach

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

We can traverse the linked list and store the reference of each visited node in a HashSet. If we encounter a node that is already present in the set, we know there is a cycle. While simple, this requires O(n) extra memory to store node references.

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 moving at different speeds:

• slow: Moves 1 node at a time (slow = slow.next).
• fast: Moves 2 nodes at a time (fast = fast.next.next).

If there is no cycle, the fast pointer will reach the end of the list (null). If there is a cycle, the fast pointer will enter the cycle and catch up to the slow pointer. When slow == fast, a cycle is detected. This is optimal because it uses constant memory.

Step-by-Step Execution Walkthrough

Let's trace the algorithm on the list 3 -> 2 -> 0 -> -4 where -4 points back to 2:

1. Step 1 (Initialization): Both slow and fast pointers are set to the head node (node 3).
   • slow = 3, fast = 3
2. Step 2 (Iteration 1):
   • slow moves 1 step to node 2.
   • fast moves 2 steps to node 0.
   • Compare pointers: slow (2) != fast (0). We continue.
3. Step 3 (Iteration 2):
   • slow moves 1 step to node 0.
   • fast moves 2 steps (from 0 to -4 and then back to 2). fast = 2.
   • Compare pointers: slow (0) != fast (2). We continue.
4. Step 4 (Iteration 3):
   • slow moves 1 step to node -4.
   • fast moves 2 steps (from 2 to 0 and then to -4). fast = -4.
   • Compare pointers: slow (-4) == fast (-4). The pointers have met!
5. Step 5 (Completion): Since slow == fast, the loop ends and the method immediately returns true, confirming the presence of a cycle.

Key Code Snippets & 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

Solving the Detect Cycle in Linked List problem highlights how we can leverage key data structures and algorithmic paradigms (like two pointers, hash maps, or dynamic programming) to significantly optimize runtime and simplify code complexity.