Detect And Remove Cycle in a Single Linked List in Java
Detecting and removing a cycle in a singly linked list is a common problem in computer science and programming. A cycle in a linked list occurs when there is a sequence of nodes in the list such that the last node points back to one of the previous nodes, creating a loop. It can lead to infinite loops and incorrect results when traversing the linked list. Detecting and removing such cycles is crucial to maintaining the integrity and correctness of linked list operations.
Approach 1: Floyd's Cycle Detection Algorithm
Floyd's Cycle Detection Algorithm, also known as the "Tortoise and Hare" algorithm, is a popular method for detecting cycles in a linked list. It uses two pointers that traverse the list at different speeds, and if there is a cycle, the two pointers will eventually meet at some point. Once a cycle is detected, the algorithm can be modified to find the starting point of the cycle and remove it if necessary.
Algorithm
Step 1: Initialize two pointers, slow and fast, to the head of the linked list. Initialize a prev pointer to keep track of the node before slow.
Step 2: Use a loop to traverse the list with the slow pointer moving one step at a time and the fast pointer moving two steps at a time.
Step 3: If there is no cycle, the fast pointer will eventually reach the end of the list (null). If there is a cycle, the fast pointer will eventually catch up with the slow pointer within the cycle.
Step 4: Reset one of the pointers (let's say fast) to the head of the list. Move both pointers one step at a time until they meet again. The meeting point will be the start of the cycle.
Step 5: Keep one pointer (slow) at the start of the list. Move the other pointer (fast) to the meeting point.
Step 6: Move both pointers one step at a time until they meet again. The meeting point will be the start of the cycle.
Step 7: Set the next pointer of the node just before the start of the cycle to null to remove the cycle. After removing the cycle, print the modified linked list.
Filename: LinkedListCycle.java
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
public class LinkedListCycle {
// Function to detect and remove cycle in a linked list
public static ListNode detectAndRemoveCycle(ListNode head) {
if (head == null || head.next == null) {
return head; // No cycle or single node, nothing to do
}
ListNode slow = head;
ListNode fast = head;
ListNode prev = null;
// Detect cycle using Floyd's algorithm
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// Cycle detected
return removeCycle(head, slow, prev);
}
prev = slow;
}
return head; // No cycle
}
// Function to remove the cycle in a linked list and return the modified head
private static ListNode removeCycle(ListNode head, ListNode meetingPoint, ListNode prev) {
ListNode slow = head;
ListNode fast = meetingPoint;
// Move slow to the start of the list and advance both slow and fast by one node
// until they meet again. The meeting point will be the start of the cycle.
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
// Move fast to the node just before the start of the cycle
while (fast.next != slow) {
fast = fast.next;
}
// Remove the cycle by setting the next of the node just before the start of the cycle to null
fast.next = null;
return head;
}
// Utility function to print the linked list with arrows
private static void printListWithArrows(ListNode head) {
while (head != null) {
System.out.print(head.val);
if (head.next != null) {
System.out.print(" -> ");
}
head = head.next;
}
System.out.println();
}
// Example usage
public static void main(String[] args) {
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
// Creating a cycle for demonstration
head.next.next.next.next.next = head.next.next;
head = detectAndRemoveCycle(head);
// Print the modified linked list with arrows
printListWithArrows(head);
}
}
Output:
1 -> 2 -> 3 -> 4 -> 5
Time Complexity
The time complexity of Floyd's Cycle Detection Algorithm for detecting and removing a cycle in a singly linked list is O(n), where n is the number of nodes in the linked list. The algorithm terminates after traversing the list once or twice, depending on whether a cycle is present.
Space Complexity
The space complexity is O(1), meaning that the algorithm uses a constant amount of extra space regardless of the size of the input linked list. This is achieved by using only a constant number of pointers (slow, fast, prev) without requiring additional data structures proportional to the input size.
Approach 2: Using HashSet
Detecting and removing a cycle in a singly linked list using a HashSet involves using a data structure to keep track of visited nodes during the traversal. This approach is straightforward and relies on the fact that if a node is revisited, it implies the presence of a cycle.
Algorithm
Step 1: Define a Node class with data and next attributes. Create a HashSet (visitedNodes) to keep track of visited nodes. Initialize two pointers (current and prev) to traverse the linked list.
Step 2: Use a while loop to traverse the linked list until the end is reached (current != null).
Step 3: Check if the current node is already in the HashSet: If it is, a loop is detected. Set the next of the previous node (prev) to null to remove the loop. Return true to indicate that a loop was removed.
Step 4: If the current node is not in the HashSet, add it to the HashSet and move to the next node. Return False if No Loop is Detected:
Step 5: If the loop exits without detecting a loop, return false to indicate that no loop was found.
Step 6: Create a utility function (printListWithArrows) to print the linked list with arrow marks between the numbers. Use this function to display the modified linked list after detecting and removing the loop.
Filename: LinkedListLoop.java
import java.util.HashSet;
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class LinkedListLoop {
// Function to detect and remove a loop in a linked list
static boolean removeLoop(Node head) {
// HashSet to keep track of visited nodes
HashSet<Node> visitedNodes = new HashSet<>();
Node current = head;
Node prev = null;
// Traverse the linked list
while (current != null) {
// Check if the current node is already visited (in the HashSet)
if (visitedNodes.contains(current)) {
// Loop detected
// Remove the loop by setting the next of the previous node to null
prev.next = null;
// Indicate that a loop was removed
return true;
} else {
// Add the current node to the HashSet
visitedNodes.add(current);
// Move to the next node
prev = current;
current = current.next;
}
}
// If the loop is not detected, return false
return false;
}
// Utility function to print the linked list with arrow marks
static void printListWithArrows(Node head) {
while (head != null) {
System.out.print(head.data);
// Add arrow mark if the next node is not null
if (head.next != null) {
System.out.print(" -> ");
}
// Move to the next node
head = head.next;
}
System.out.println();
}
// Example usage
public static void main(String[] args) {
// Create a linked list: 1 -> 2 -> 3 -> 4 -> 5
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
// Creating a loop for demonstration (5 points back to 3)
head.next.next.next.next.next = head.next.next;
// Detect and remove the loop
boolean loopRemoved = removeLoop(head);
// Display a message based on whether a loop was removed or not
if (loopRemoved) {
System.out.println("Loop removed from the linked list");
} else {
System.out.println("No loop found in the linked list");
}
// Print the modified linked list with arrow marks
printListWithArrows(head);
}
}
Output:
Loop removed from the linked list
1-> 2 -> 3 -> 4 -> 5
Time Complexity
The time complexity of the algorithm is O(n), where n is the number of nodes in the linked list. In the worst case, the algorithm traverses the entire linked list once to detect the loop, and possibly a second time to remove the loop.
Space Complexity
The space complexity is O(n), where n is the number of nodes in the linked list. The algorithm uses a HashSet to keep track of visited nodes. In the worst case, all nodes will be stored in the HashSet.