Home » Link Lists(Nuts & Bolts of CS)

# Link Lists(Nuts & Bolts of CS)

Below diagram shows a linked list with a loop. detectAndRemoveLoop() must change the below list to 1->2->3->4->5->NULL.We can also use Floyd Cycle Detection algorithm to detect and remove the loop. In the Floyd’s algo, the slow and fast pointers meet at a loop node. We can use this loop node to remove cycle. There are following two different ways of removing loop when Floyd’s algorithm is used for Loop detection.

CODE-

```
class Node {
Object data;
Node next;
}

public class FloydCycleFindingAlgorithm {

/**
* Detects and removes a cycle in a linked list. Returns true if a cycle was
* found and removed; or false otherwise.
*/
public static boolean removeCycle( Node head ) {

// Search for a cycle
while( tortoise != hare && hare.next != null )
{ // 2 condition: if not null then must be loop. this cond. can be removed also
tortoise = tortoise.next;
System.out.println( "tortoise is = "+tortoise.data );

hare = hare.next.next; //hare.next=B,b.next=C
System.out.println( "hare is = "+hare.data );

}

// Check if a cycle was found
if( tortoise != hare ) {
return false;
}

else
{
// Find the node from which the cycle starts
Node tort = head; /// tort =B, hare=D
while( hare.next != tort ) // D.next!=B ; increment both
{
tort = tort.next;
hare = hare.next;
}

// Remove cycle
hare.next = null;
}
return true;
}

/**
* Test Method
*/
public static void main( String[ ] args ) {

//
Node nodeA = new Node( );
Node nodeB = new Node( );
Node nodeC = new Node( );
Node nodeD = new Node( );
Node nodeE = new Node( );

nodeA.data = "A"; nodeA.next = nodeB;
nodeB.data = "B"; nodeB.next = nodeC;
nodeC.data = "C"; nodeC.next = nodeD;

// Introduce a cycle in the linked-list

nodeD.data = "D"; nodeD.next = nodeB;

// Test for the presence of a cycle.

if(removeCycle( nodeA ) ) {
System.out.println( "Cycle detected and removed!" );
} else {
System.out.println( "No cycle detected." );
}

// Iterating through the linked list
//
for( Node cursor = nodeA; cursor != null; cursor = cursor.next ) {
System.out.print( cursor.data + ( cursor.next != null ? " -> " : "" ) );
//-> will be applied till cursor.next != null i.e. values a b c d are there else(:) " "
}
}
}

```

## 1 Comment

1. Ajeeth Kapoor says:

Hi Man,

Interesting piece!Great to see someone write Link Lists(Nuts & Bolts of CS) who is not a fanatic or a complete skeptic.

I tried to sign-up for AWS a few days ago. I can use the Management Console but I’d like to start using Lambda. However I keep getting a page saying “Your service sign-up is almost complete!” AWS Tutorial

I read multiple articles and watched many videos about how to use this tool – and was still confused! Your instructions were easy to understand and made the process simple.

Many Thanks,
Ajeeth

### Website

#### arpit tak

I like JAVA . I code. I chill. I blog.I eat. I sleep. I dream.