Removing the cycle from a linked list in Java

In this article, we will be learning how to remove a cycle or loop from a linked list in Java.

Linked lists are linear data structures that store nodes having- data and a pointer that points to the address of the next node, thereby linking the nodes. A linked list with loop looks like:-

linked list cycle

Prior knowledge of Linked List Data Structure in Java and detecting a loop with Floyd’s Cycle detection will be helpful to understand the implementation.

Implementation to remove a cycle from a linked list in Java:

In this method, two pointers: fast and slow, traverse the linked list.  Likewise, the fast pointer moves ahead of the slow pointer while traversing. Specifically, the point where the fast pointer meets the slow pointer indicates the presence of a cycle in the list.

class Loop_LL { 
static NODE heaD; 
static class NODE
{ 
int datA; 
NODE nexT; 
NODE(int x) { 
datA = x; 
nexT = null; }} 
int find_remove_loop(NODE nodE) { 
NODE slow_pointer = nodE, fast_pointer = nodE; 
while (slow_pointer != null && fast_pointer != null && fast_pointer.nexT != null) { 
slow_pointer = slow_pointer.nexT; 
fast_pointer = fast_pointer.nexT.nexT; 
// condition to check if loop exists
if (slow_pointer == fast_pointer) { 
loop_removal(slow_pointer, nodE); 
return 1;} 
} 
return 0; 
}

Remove a cycle or loop:

Subsequently, the slow pointer and the loop node are passed as parameters for the loop removal function. From the beginning of the list, a pointer traverses until it finds the first node of the list. Meanwhile, a second pointer starts traversing from the loop node. If the first and second pointer meets, there’s a loop. Remove this loop by making the second pointer’s next to point at the first pointer, thereby eliminating the loop node.

void loop_removal(NODE loop, NODE current_pointer) { 
NODE pointer_1 = null, pointer_2 = null;
pointer_1 = current_pointer; 
while (1 == 1) { 
pointer_2 = loop; 
while (pointer_2.nexT != loop && pointer_2.nexT != pointer_1) { 
pointer_2 = pointer_2.nexT;} 
if (pointer_2.nexT == pointer_1) { 
break; }
pointer_1 = pointer_1.nexT;} 
pointer_2.nexT = null;}
void final_lin_list_display(NODE nodE) 
{ 
while (nodE != null) { 
System.out.print(nodE.datA + " "); 
nodE = nodE.nexT; 
}}

Main section:

Having declared all functions to detect and remove cycle, we now move on to calling the functions. Following is the main section to check and test for loops:

public static void main(String[] args){ 
    Loop_LL lin_list = new Loop_LL(); 
    lin_list.heaD = new NODE(321); 
    lin_list.heaD.nexT = new NODE(123); 
    lin_list.heaD.nexT.nexT = new NODE(231); 
    lin_list.heaD.nexT.nexT.nexT = new NODE(100); 
    lin_list.heaD.nexT.nexT.nexT.nexT = new NODE(101);
    lin_list.heaD.nexT.nexT.nexT.nexT.nexT=new NODE(110);
    lin_list.heaD.nexT.nexT.nexT.nexT.nexT.nexT=new NODE(7);
    heaD.nexT.nexT.nexT.nexT.nexT.nexT = heaD.nexT.nexT.nexT; 
    lin_list.find_remove_loop(heaD); 
    System.out.println("Linked List after removing loop : "); 
    lin_list.final_lin_list_display(heaD); 
}}

Output:

The above code generates the following output:-

C:\Users\KIRA\Desktop>javac Loop_LL.java
C:\Users\KIRA\Desktop>java Loop_LL
Linked List after removing loop :
321 123 231 100 101 110

I hope you like the article, feel free to comment down your queries.

Leave a Reply

Your email address will not be published. Required fields are marked *