How can one find a cycle in the linked list? IF found how
to recognize the cycle and delete that cycle?

Answers were Sorted based on User's Feedback



How can one find a cycle in the linked list? IF found how to recognize the cycle and delete that c..

Answer / monti

bool find_cycle(Node* head){
Node* ptr1 = head;
Node* ptr2 = head;

while(ptr1 != NULL && ptr2 != NULL && ptr2->next != NULL){
if(ptr1 == ptr2){
printf("\nClycle present in thr LinkList\n");
return true;
}
ptr1 = prt1->next;
ptr2 = ptr2->next->next;
}
return false;
}

Is This Answer Correct ?    36 Yes 14 No

How can one find a cycle in the linked list? IF found how to recognize the cycle and delete that c..

Answer / kamran

As far as answer 2 is concerned..it is not correct because
ptr1 and ptr2 is both pointing towards Head. and below
while loop true at first attempt and both the pointer are
still pointing toward head so at first etration condition
will be true even though there is no loop :)

The modified verision is this
bool find_cycle(Node* head){
Node* ptr1 = head;
Node* ptr2 = head->next;

while(ptr1 != NULL && ptr2 != NULL && ptr2->next != NULL)
{
if(ptr1 == ptr2){
printf("\nClycle present in thr LinkList\n");
return true;
}
ptr1 = prt1->next;
ptr2 = ptr2->next->next;
}
return false;
}

Is This Answer Correct ?    18 Yes 1 No

How can one find a cycle in the linked list? IF found how to recognize the cycle and delete that c..

Answer / monti

Well, Answer-3 is correct but only for link list of type 'O'
but it fails for link list of type '9' (which also have a
circle). So to cover up all possibilities answer 2 should be
followed.

Is This Answer Correct ?    13 Yes 0 No

How can one find a cycle in the linked list? IF found how to recognize the cycle and delete that c..

Answer / kedar

Ans #6 is the correct version.

//ensure that it not a empty list or list with single node
or list with 2 nodes which is not a cycle.

bool find_cycle(Node* head){

if(head == NULL // empty list
|| head->next == NULL // list with 1 node
|| head->next>next == NULL) // 2 nodes w/o cycle
{
return false;
}

Node* ptr1 = head;
Node* ptr2 = head->next;

while(ptr1 != NULL && ptr2 != NULL && ptr2->next != NULL)
{
if(ptr1 == ptr2){
printf("\nClycle present in thr LinkList\n");
return true;
}
ptr1 = prt1->next;
ptr2 = ptr2->next->next;
}
return false;
}

Is This Answer Correct ?    8 Yes 0 No

How can one find a cycle in the linked list? IF found how to recognize the cycle and delete that c..

Answer / kannan

If the address part of the node contains the header address
then cycle is formed Is it so...

Is This Answer Correct ?    21 Yes 16 No

How can one find a cycle in the linked list? IF found how to recognize the cycle and delete that c..

Answer / vishal

a cycle is not only a link between the last node of list and
the first node of the list ..but a cycle can also be present
from the last node to the second,third,fourth node of the
list....

implementing using recursive functions.....
boolean hasloop(struct node *start)
{
if(start!=NULL)//stop condition for recursive function
{
currentnode=start;
while(currentnode!=NULL)
{
currentnode=currentnode->link;
if(start==currentnode)//cycle detected
{
return true;
}
}
}

return false;//cycle not detected

}

Is This Answer Correct ?    5 Yes 0 No

How can one find a cycle in the linked list? IF found how to recognize the cycle and delete that c..

Answer / monti

Ok guys now you all know the answer of "How to find if a
list has a cycle or not"...now answer this "Give an optimal
solution to return the stating point of cycle in a link-list
if it contains a cycle or else return NULL. You are given
head of that link-list"

Is This Answer Correct ?    4 Yes 0 No

How can one find a cycle in the linked list? IF found how to recognize the cycle and delete that c..

Answer / rajdeep...

Monti,
in ur ans what is the solution for the linked list having
two nodes but not circular....

Is This Answer Correct ?    1 Yes 0 No

How can one find a cycle in the linked list? IF found how to recognize the cycle and delete that c..

Answer / shankhasubhra mukherjee

this is a same as Circular link list. try it now.

Is This Answer Correct ?    2 Yes 2 No

How can one find a cycle in the linked list? IF found how to recognize the cycle and delete that c..

Answer / chethu

Why are you guys moving both the pointers one behind the other?
You can keep a pointer at the header and traverse the other and check if it comes back to header if it does then there is a cycle else there is no cycle..

bool find_cycle(Node* head){
Node* ptr1 = head;
Node* ptr2 = head->next;

while(ptr2 != NULL && ptr2->next != NULL)
{
if(ptr1 == ptr2){
printf("\nClycle present in thr LinkList\n");
return true;
}
ptr2 = ptr2->next->next;
}
return false;
}

This should be more efficient.

Is This Answer Correct ?    1 Yes 1 No

Post New Answer

More Data Structures Interview Questions

What is stack in geography?

0 Answers  


What is the difference between classifying and sorting?

0 Answers  


What do you mean by selection sort?

0 Answers  


Is hashtable fail fast?

0 Answers  


How many different binary trees and binary search trees can be made from three nodes that contain the key values 1, 2 & 3?

28 Answers   Accenture, Amazon, College School Exams Tests, iGate, Microsoft, TCS, Wipro,






Is hashmap ordered?

0 Answers  


How to reference all the elements in a one-dimension array?

0 Answers  


What is the difference between Array and Array List ? Explain in brief with example.

0 Answers   MCN Solutions,


Can treemap have null values?

0 Answers  


When will you use array over arraylist?

0 Answers  


Can you make an arraylist of arrays?

0 Answers  


What is heap tree explain with example?

0 Answers  


Categories