Interested to Buy Any Domain ? << Click Here >> for more details...
How would you find a cycle in a linked list?
- 3 Answers
- 13498 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 wrong with this program statement? void = 10;
Explain how can I remove the trailing spaces from a string?
What are the languages are portable and platform independent?Why they are like that?
5) Write a program that takes a 3 digit number n and finds out whether the number 2^n + 1 is prime, or if it is not prime find out its factors.without using big int and exponential function
What is the use of bitwise operator?
how do we remove the printed character in printf statement and write next it it
How can variables be characterized?
3.write a simple program that will output your name,phone number,e-mail address,and academic major on separate lines 1.create an account and a personal directory for your work b.find out how to create a subdirectory on your system.create one called info c.you will use a text editor to type in your programs and data files.some C systems have a built in text editor;others do not.Find out what text editor you will be using and how to access it.create a text file(not a program) containing your name ,address,and telephone number on separate lines.Next,write the brand of computer you are using and the name of the text editor.Then write a paragraph that describes your past experience with computers.save this file in your info directory. d. find out how to print a file on your system .print out and turn in the file you created in (c).
This is a variation of the call_me function in the previous question:call_me (myvar)int *myvar;{ *myvar += 5; }The correct way to call this function from main() will be a) call_me(myvar) b) call_me(*myvar) c) call_me(&myvar) d) expanded memory
Write a program to use switch statement.
0 Answers Agilent, Integreon, ZS Associates,
int *a[5] refers to
main() { int i = 10; printf(" %d %d %d \n", ++i, i++, ++i); }
C 
