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 ;
}
