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
- Create the Linked List and Node Structure: Define a
Node
class to represent each element in the linked list and aLinkedList
class to manage the list. - Add Nodes to the Linked List: Implement methods to add nodes to the linked list.
- 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.
- 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.
- 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 containsdata
and a reference to thenext
node in the list. - The constructor initializes the node with data and sets the
next
pointer tonull
.
Step 2: Initialize the LinkedList Class
- The
LinkedList
class manages the linked list. The class contains thehead
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, thehead
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
andfast
, are initialized at thehead
. slow
moves one step at a time, whilefast
moves two steps at a time.- If there is a cycle,
slow
andfast
will eventually meet inside the cycle. - If
fast
reaches the end of the list (null
), there is no cycle.
- Two pointers,
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.