Remove Loop in Linked List Using Java

A loop in a linked list forms when a node points back to an earlier node, creating a cycle instead of ending the list. Detecting and removing this loop restores the list's linear structure, preventing infinite traversal and improving its reliability for further operations.

Approach: Using Hashing

This method uses a HashSet to store visited nodes while traversing the linked list. If a node is revisited (already in the HashSet), a loop is detected and removed by updating the previous node's next pointer to null.

Algorithm

Step 1: Create an empty HashSet to store visited nodes and a variable previousNode to track the previous node.

Step 2: Start from the head node and traverse through the linked list, checking each node.

Step 3: For each node, check if it's already in the HashSet (indicating a loop). If a loop is detected, remove it by setting previousNode.next = null.

Step 4: If no loop is detected, add the current node to the HashSet and move to the next node.

Step 5: Continue until the end of the list is reached (i.e., headNode becomes null), ensuring the loop is removed if it exists.

Implementation

File Name: LinkedListLoopRemover.java

Output:

 5 12 7 3 8 

Time Complexity: O(N) - Traverses each node once.

Auxiliary Space: O(N) - Uses a HashSet to store visited nodes.

Approach: Floyd's Cycle Detection Algorithm

Floyd's Cycle Detection Algorithm, also known as the Tortoise and Hare approach, uses two pointers moving at different speeds to detect a loop in a linked list. If a cycle exists, the two pointers will meet inside the loop, allowing for efficient detection and removal with constant space complexity.

Algorithm

Step 1: Set two pointers, slowPointer and fastPointer, at the head of the linked list.

Step 2: Move slowPointer one step and fastPointer two steps forward. If they meet, a loop is detected.

Step 3: Reset slowPointer to the head. Move both slowPointer and fastPointer one step at a time until they meet at the start of the loop.

Step 4: Once the start of the loop is found, set the last node's nextNode pointer to null to break the loop.

Step 5: Print the linked list from the head to confirm the loop is removed.

Implementation

File Name: LinkedListLoopRemover.java

Output:

 100 200 300 400 500 

Time Complexity: O(n)

Auxiliary Space Complexity: O(1)