Detecting a Cycle in a Linked List using Java

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

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.