Detecting a Cycle in a Linked List using Java

Detecting a cycle in a linked list is one of the common questions asked in interviews. Detecting a loop or cycle means checking whether any node in the linked list points back to a previous node, which indicates a circular reference. A widely accepted approach for detecting a cycle in a linked list is Floyd's Cycle Detection Algorithm, often called the "Tortoise and the Hare" approach. 

How the Algorithm Works

Two Pointers: We maintain two pointers, one called tortoise and the other hare. The tortoise moves one step at a time while the hare moves two steps. 

Loop Detection: If there's a loop, the hare will eventually meet the tortoise inside the loop. 

No Loop: If there isn't a loop, the hare will reach the end of the linked list. 

Let's look at the Java program that uses this approach to detect a cycle in a linked list. 

Java program to detect a cycle in a Linked List

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class CycleDetection {

    public static boolean hasCycle(Node head) {
        if (head == null || head.next == null) {
            return false;
        }

        Node tortoise = head;
        Node hare = head.next;

        while (tortoise != hare) {
            if (hare == null || hare.next == null) {
                return false;  // Hare reached the end without looping
            }
            tortoise = tortoise.next;
            hare = hare.next.next;
        }

        // If tortoise and hare meet, there's a cycle
        return true;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);

        System.out.println("Has Cycle: " + hasCycle(head));  // Should return false

        // Introducing a cycle: Node 4 points back to Node 2
        head.next.next.next.next = head.next;

        System.out.println("Has Cycle: " + hasCycle(head));  // Should return true
    }
}

Output:

Has Cycle: false
Has Cycle: true

Explanation: 

We first define a Node class to represent the elements of our linked list. 

In the hasCycle function, we implement Floyd's cycle detection algorithm. 

We set two pointers, tortoise and hare, where the tortoise moves one step at a time and the hare moves two. 

If there's a cycle, both pointers will eventually point to the same node, and the function will return true. If there's no cycle, the hare (which moves faster) will reach the end of the list, and the function will return false. 

In the main function, we create a linked list and test it for cycles. Initially, the list has no cycles, and the output is false. After introducing a cycle by making the last node point back to the second node, the output becomes true. 

By understanding this algorithm and the provided Java program, one can efficiently detect cycles in a linked list, a skill that might come in handy in both software development and technical interviews.