How can one find a cycle in the linked list? IF found how
to recognize the cycle and delete that cycle?
- 12 Answers
- 20565 Views
- Citrix, I also Faced
- E-Mail Answers
Answers were Sorted based on User's Feedback
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
Answer / shankhasubhra mukherjee
this is a same as Circular link list. try it now.
| Is This Answer Correct ? | 2 Yes | 2 No |
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 |
What is the idea behind splaying?
State the difference between stacks and linked lists?
What do you mean by hash table?
How to check array contains value or not?
Why linked list is required?
Who invented data structure?
Write the postfix form of the expression: (a + b) * (c - d)
What are the notations used in Evaluation of Arithmetic Expressions using prefix and postfix forms?
Explain the difference between a list and array.
Is merge sort better than quick?
Is file a data structure?
What is a reverse linked list.
Windows 
