How would you find a cycle in a linked list?

Answer Posted / 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



Post New Answer       View All Answers


Please Help Members By Posting Answers For Below Questions

WRITE A PROGRAM TO MERGE TWO SORTED ARRAY USING MERGE SORT TECHNIQUE..

1811


Is javascript written in c?

792


Write a program to find factorial of a number using recursive function.

858


How can a process change an environment variable in its caller?

927


With the help of using classes, write a program to add two numbers.

842


How can I delete a file?

833


What is spark map function?

808


What is adt in c programming?

854


Explain about the functions strcat() and strcmp()?

792


What are volatile variables in c?

701


How do you convert a decimal number to its hexa-decimal equivalent.Give a C code to do the same

873


What is huge pointer in c?

769


Write a program for finding factorial of a number.

848


write a program for the normal snake games find in most of the mobiles.

2022


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

1000