Detecting a Cycle in a Linked List using Java

Introduction

A cycle in a linked list occurs when a node's next pointer points back to one of the previous nodes in the list, forming a loop. Detecting such a cycle is an important problem in data structures, especially in algorithms that involve linked lists. A common method to detect a cycle in a linked list is Floyd's Cycle Detection Algorithm, also known as the Tortoise and Hare algorithm.

Problem Statement

Create a Java program that:

• Defines a singly linked list.
• Detects whether a cycle exists in the linked list using Floyd's Cycle Detection Algorithm.

Example 1:

• Input: 1 -> 2 -> 3 -> 4 -> 5 -> 2 (where the last node points back to the second node)
• Output: Cycle detected in the linked list

Example 2:

• Input: 1 -> 2 -> 3 -> 4 -> 5 -> null (no cycle)
• Output: No cycle detected in the linked list

Solution Steps

1. Define the Node Class: Create a class to represent a node in the linked list, containing data and a reference to the next node.
2. Define the LinkedList Class: Create a class to manage the linked list, including methods to insert elements and detect a cycle using Floyd's Cycle Detection Algorithm.
3. Detect a Cycle: Implement the cycle detection algorithm by using two pointers (slow and fast) that move at different speeds through the list.
4. Display the Result: Print whether a cycle was detected in the linked list.

Java Program

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;
    }
}

class LinkedList {
    Node head;

    // Method to insert a new node at the end of the list
    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // Method to create a cycle in the linked list for testing
    public void createCycle(int position) {
        if (position < 1) {
            return;
        }
        Node current = head;
        Node cycleNode = null;
        int count = 1;
        while (current.next != null) {
            if (count == position) {
                cycleNode = current;
            }
            current = current.next;
            count++;
        }
        current.next = cycleNode; // Create a cycle by pointing the last node to the cycleNode
    }

    // Method to detect a cycle in the linked list using Floyd's Cycle Detection Algorithm
    public boolean detectCycle() {
        if (head == null) {
            return false;
        }
        Node slow = head;
        Node fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;         // Move slow pointer by 1
            fast = fast.next.next;    // Move fast pointer by 2

            if (slow == fast) {       // If they meet, a cycle exists
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Insert elements into the linked list
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);
        list.insert(5);

        // Optionally create a cycle in the linked list for testing
        list.createCycle(2); // Creates a cycle where the last node points to the second node

        // Detect a cycle in the linked list
        boolean hasCycle = list.detectCycle();

        // Display the result
        if (hasCycle) {
            System.out.println("Cycle detected in the linked list");
        } else {
            System.out.println("No cycle detected in the linked list");
        }
    }
}

Explanation

• Node Class: This class defines a node in the linked list, with an integer data and a next pointer to the next node in the list.

• LinkedList Class: This class manages the linked list and provides methods to insert nodes, create a cycle for testing, and detect a cycle using Floyd's Cycle Detection Algorithm.

  • insert(int data): Adds a new node with the given data at the end of the list.

  • createCycle(int position): Creates a cycle in the linked list by connecting the last node to the node at the given position.

  • detectCycle(): Detects a cycle in the linked list by using two pointers (slow and fast). The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there is a cycle, the two pointers will eventually meet.

• Main Method: The main method demonstrates the functionality by creating a linked list, optionally creating a cycle, and then detecting if a cycle exists.

Output Example

Example 1 (With Cycle):

Cycle detected in the linked list

Example 2 (Without Cycle):

No cycle detected in the linked list

Conclusion

This Java program effectively detects a cycle in a singly linked list using Floyd's Cycle Detection Algorithm (Tortoise and Hare). By using two pointers that move at different speeds, the algorithm can efficiently determine whether a cycle exists. This method is commonly used in various applications where linked lists are involved, such as in data structures and algorithms.