Java Program to Detect a Cycle in a Linked List

Introduction

A cycle in a linked list occurs when a node’s next pointer points back to a previous node, creating a loop in the list. Detecting such a cycle is crucial to prevent infinite loops and potential memory issues in various applications. This guide will walk you through writing a Java program that detects a cycle in a singly linked list using Floyd’s Cycle Detection Algorithm, also known as the Tortoise and Hare algorithm.

Problem Statement

Create a Java program that:

  • Implements a singly linked list.
  • Detects whether a cycle exists in the linked list using Floyd’s Cycle Detection Algorithm.
  • Displays a message indicating whether a cycle is present.

Example:

  • Input: A linked list where a node’s next pointer points back to a previous node, creating a cycle.
  • Output: "Cycle detected in the linked list."
  • Input: A linked list with no cycle.
  • Output: "No cycle detected in the linked list."

Solution Steps

  1. Create the Linked List and Node Structure: Define a Node class to represent each element in the linked list and a LinkedList class to manage the list.
  2. Add Nodes to the Linked List: Implement methods to add nodes to the linked list.
  3. Create a Cycle (for testing purposes): Implement a method to create a cycle in the linked list by making a node point back to a previous node.
  4. Detect the Cycle:
  • Implement Floyd’s Cycle Detection Algorithm using two pointers: a slow pointer and a fast pointer.
  • The slow pointer moves one step at a time, while the fast pointer moves two steps.
  • If there is a cycle, the fast pointer will eventually meet the slow pointer.
  1. Display the Result: Output whether a cycle is detected or not.

Java Program

// Java Program to Detect a Cycle in a Linked List
// Author: https://www.rameshfadatare.com/

class Node {
    int data;
    Node next;

    // Constructor to initialize the node
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    // Method to add a new node at the end of the list
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            // Step 1: Initialize the head if the list is empty
            head = newNode;
        } else {
            // Step 2: Traverse to the end of the list and add the new node
            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 <= 0) return;

        Node cycleNode = null;
        Node current = head;
        int count = 1;
        
        // Step 3: Traverse the list to find the node at the given position
        while (current != null) {
            if (count == position) {
                cycleNode = current;
            }
            if (current.next == null) {
                // Step 4: Create a cycle by pointing the last node to the cycleNode
                current.next = cycleNode;
                return;
            }
            current = current.next;
            count++;
        }
    }

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

        // Step 5: Initialize two pointers, slow and fast
        Node slow = head;
        Node fast = head;

        // Step 6: Traverse the list with the two pointers
        while (fast != null && fast.next != null) {
            slow = slow.next;          // Move slow pointer by one step
            fast = fast.next.next;     // Move fast pointer by two steps

            if (slow == fast) {
                // Step 7: If slow and fast meet, a cycle is detected
                return true;
            }
        }
        // Step 8: If the loop ends, no cycle is detected
        return false;
    }
}

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

        // Adding elements to the linked list
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        // Creating a cycle in the linked list (e.g., connecting last node to the second node)
        list.createCycle(2);

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

Explanation

Step 1: Initialize the Node Class

  • The Node class represents a single node in the linked list. Each node contains data and a reference to the next node in the list.
  • The constructor initializes the node with data and sets the next pointer to null.

Step 2: Initialize the LinkedList Class

  • The LinkedList class manages the linked list. The class contains the head node that points to the first node in the list.
  • The add() method appends a new node to the end of the list. If the list is empty, the head node is set to the new node.

Step 3: Create a Cycle in the Linked List (Optional for Testing)

  • The createCycle() method is used to create a cycle in the linked list by pointing the last node to a node at a specified position. This step is crucial for testing the cycle detection algorithm.

Step 4: Detect a Cycle Using Floyd’s Cycle Detection Algorithm

  • The detectCycle() method implements Floyd’s Cycle Detection Algorithm:
    • Two pointers, slow and fast, are initialized at the head.
    • slow moves one step at a time, while fast moves two steps at a time.
    • If there is a cycle, slow and fast will eventually meet inside the cycle.
    • If fast reaches the end of the list (null), there is no cycle.

Step 5: Display the Result

  • The program checks the result of the detectCycle() method and prints whether a cycle was detected or not.

Output Example

Example with a Cycle:

Cycle detected in the linked list.

Example without a Cycle:

If you comment out the list.createCycle(2); line, the output will be:

No cycle detected in the linked list.

Conclusion

This Java program demonstrates how to detect a cycle in a singly linked list using Floyd’s Cycle Detection Algorithm. The program covers essential concepts such as linked list manipulation, node traversal, and cycle detection. This exercise is valuable for understanding how to efficiently manage linked lists and detect cycles in Java programming.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top