🎓 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
- Define the Node Class: Create a class to represent a node in the linked list, containing data and a reference to the next node.
- 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.
- Detect a Cycle: Implement the cycle detection algorithm by using two pointers (slow and fast) that move at different speeds through the list.
- 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
dataand anextpointer 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 (
slowandfast). 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
mainmethod 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.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment