####
Interview Question

Given a linked list, find if it contains a cycle, and if so, remove the cycle. Below is an example of a linked list with a cycle:

####
Solution

Using the same method of Floyd's Cycle Detection Algorithm to detect a cycle or a loop in a linked list, from here, we can remove the cycle from the linked list using the node where both the fast and slow pointers coincided in the Floyd's algorithm. We take two more temporary pointers and move them as shown below. **itr **is initialised to head node which **temp **is initialised to **fast**. Now, **temp** will move in the circle marked with red arrows, while **itr** will traverse in the direction marked by black arrows. When **itr** and the next node of **temp** (**temp -> next**) meet, then that is the point where **temp -> next** points to first node of cycle and temp itself points to last element of cycle. We now just have to change the **temp -> next** pointer to point to null instead of another node which created a cycle.

#include <stdio.h>
#include <stdlib.h>
struct node {
int data ;
struct node * next ;
} * head = NULL ;
void push ( int val )
{
struct node * newnode = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
newnode -> data = val ;
newnode -> next = NULL ;
struct node * ptr = head ;
if ( ptr == NULL )
head = newnode ;
else
{
while ( ptr -> next )
ptr = ptr -> next ;
ptr -> next = newnode ;
}
}
void print ()
{
struct node * itr ;
itr = head ;
while ( itr )
{
printf ( " %d " , itr -> data ) ;
itr = itr -> next ;
}
}
void find ()
{
int flag = 1 ;
struct node * fast , * slow , * itr , * temp ;
fast = head ;
slow = head ;
if ( head )
{
while ( fast -> next && slow -> next )
{
fast = fast -> next -> next ;
slow = slow -> next ;
if ( fast == slow )
{
printf ( " The linked list contains a cycle. \n" ) ;
flag = 0 ;
break ;
}
}
if ( flag )
{
printf ( " The linked list does not contain a cycle. \n" ) ;
return ;
}
}
itr = head ;
while ( 1 )
{
temp = fast ;
while ( temp -> next != fast && temp -> next != itr )
temp = temp -> next ;
if ( temp -> next == itr )
break ;
itr = itr -> next ;
}
temp -> next = NULL ;
}
int main ()
{
push ( 2 ) ;
push ( 3 ) ;
push ( 1 ) ;
push ( 8 ) ;
push ( 7 ) ;
print () ;
head -> next -> next -> next -> next -> next = head -> next -> next ;
find () ;
print () ;
return 0 ;
}