How would you find a cycle in a linked list?
- 3 Answers
- 12410 Views
- NSN, I also Faced
- E-Mail Answers
Answers were Sorted based on User's Feedback
Answer / sujith
Simultaneously go through the list by ones (slow iterator)
and by twos (fast iterator). If there is a loop the fast
iterator will go around that loop twice as fast as the slow
iterator. The fast iterator will lap the slow iterator
within a single pass through the cycle. Detecting a loop is
then just detecting that the slow iterator has been lapped
by the fast iterator.
This solution is "Floyd's Cycle-Finding Algorithm" as
published in "Non-deterministic Algorithms" by Robert W.
Floyd in 1967. It is also called "The Tortoise and the Hare
Algorithm"
| Is This Answer Correct ? | 11 Yes | 2 No |
Answer / jaroosh
The above method is working of course, but is not the most
efficient. Other methods are however quite complex and not
so easy to explain.
Anyway, to exemplify this aforementioned method, maybe not
the most efficient code, but off the top of my head, hope
there are no misspellings.
bool isCyclic(LinkedNode *list)
{
if(list == NULL || list->next == NULL) return false;
LinkedNode *node1 = list, *node2 = node1->next;
while(node1 != node2)
{
if(node1==NULL || node2==NULL || node2->next == NULL)
return false;
node1 = node1->next;
node2= node2->next->next;
}
return true;
}
NOTE: the assumption is that for noncyclic list, the last
node has next pointer set to NULL.
| Is This Answer Correct ? | 6 Yes | 7 No |
Answer / amit
the last node of the list will have address of first node
then it is a cycle linked list.
| Is This Answer Correct ? | 4 Yes | 11 No |
What is a volatile keyword in c?
What are runtime error?
If a variable is a pointer to a structure, then which operator is used to access data members of the structure through the pointer variable?
Difference between malloc() and calloc() function?
number of times a digit is present in a number
2)#include<iostream.h> main() { printf("Hello World"); } the program prints Hello World without changing main() the o/p should be intialisation Hello World Desruct the changes should be a)iostream operator<<(iostream os, char*s) os<<'intialisation'<<(Hello World)<<Destruct b) c) d)none of the above
Explain which of the following operators is incorrect and why? ( >=, <=, <>, ==)
void swap(int a,int b) { a=a+b; b=a-b; a=a-b; } in this code always gives the same result for all case
every function has return the value?
Write a code of a general series where the next element is the sum of last k terms.
How can I do serial ("comm") port I/O?
When can you use a pointer with a function?
C 
