Interview Question
Given a linked list, find out if it has a cycle or not. An example of a linked list with a cycle is :
Solution
There are two ways to solve this problem: One is to use hashing, where we maintain a hash table to keep track of all visited nodes, and if a node is being visited again, then we know that the linked list contains a cycle.
The other method is to maintain two pointers - one slow and other fast, and if the two are at any point equal (except at the beginning when they point to the head / first node), then the linked list is said to contain a cycle. This method is the solution interviewers are looking forward to.
#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 ;
}
}
int find ()
{
struct node * fast , * slow ;
fast = head ;
slow = head ;
if ( head )
{
while ( fast -> next && slow -> next )
{
fast = fast -> next -> next ;
slow = slow -> next ;
if ( fast == slow )
return 1 ;
}
}
return 0 ;
}
int main ()
{
push ( 2 ) ;
push ( 3 ) ;
push ( 1 ) ;
push ( 8 ) ;
push ( 7 ) ;
print () ;
head -> next -> next -> next -> next -> next = head -> next -> next ;
if ( find () )
printf ( " The linked list contains a cycle. " ) ;
else printf ( " The linked list does not contain a cycle. " ) ;
printf ( " \n ") ;
return 0 ;
}
