Amazon Interview Question Software Engineer / Developers
have two pointers in a list. a and b
b points to two locations ahead of a so every time a->next->next = b.
if there is a loop at any point u ll keep going through the many times depending on the size of the loop and eventually in a circular loop u ll get b->next = a.
return there.. elese it just means it is a big list... gotta better answer?
Keep two pointers - One stationary pointer and another moving pointer.
Move the "moving pointer" and traverse the list one by one. At a time both pointers will be equal if it is a cyclic list
void function(node *start)
{
if(start==NULL)
{
cout<<"Empty list"<<endl;
return;
}
if(start==start->next)
{
cout<<"circular"<<endl;
return;
}
else if(start->next==NULL)
{
cout<<"not circular"<<endl;
return;
}
node *ptr=start->next;
while(ptr->next!=NULL && ptr!=start)
ptr=ptr->next;
if(ptr->next==NULL)
{
cout<<"not circular"<<endl;
return;
}
else
cout<<"Circular"<<endl;
}
}
How about this
1. Go to the last node of that linked list.
2. check if lastNode.Link == null, then it is a singly linked list. Or it is circular.
we can never know about the last node if we dont know that whether it is circular list or not because check condition get changed for normal list while(ptr!=NULL) and for circular its while(ptr==start)..... So ...
ptr=start->next
while(1)
{
if(ptr==null)
{list is not cirular;
exit(0);}
elseif(ptr=start)
{list is circular
exit(0)}
else
{ptr=ptr->next};
}
Use Hare and tortoise alogirthm as circular linked list is nothing but loop in a linked list.
- aravinds86 February 07, 2010