hey can someone tell me how to find a loop in a linked list....ive searched a lot on google.i found the famous floyed`s algorithm but what i dont understand is that how can this algorithm if the length of the loop is bigger than 4 node...as in what if a have a linked list that goes on like
a->b->c->d->e->f->g->h->i->j->k->l->m->b.....
could someone please suggest an algorithm for this or if floyd s works for this then how?
you may try this-
introduce a counter variable in the basic element structure and initialize it to 0. starting from 'a', start iterating through the elements. before moving on to the next element, increment the counter variable by 1 and then check its value, if value>1, there exists a loop as this element has been encountered before, if value <= 1, then move on to the next element.
you may also achieve it by defining a 2-d array which stores the memory address of elements and their corresponding encounters during iteration.
Floyds alogorithm(Tortoise and hare algorithm) should suffice your case also. When there is a loop the hare is stuck in the loop however fast it runs and the tortoise will eventually catch up. For a very good discussion see here Interview: Remove Loop in linked list - Java - Stack Overflow
