java - What is an efficient algorithm to find whether a singly linked list is circular/cyclic or not? -


this question has answer here:

how can find whether singly linked list circular/cyclic or not? tried search couldn't find satisfactory solution. if possible, can provide pseudo-code or java-implementation?

for instance:
135714575, second 5 third element of list.

the standard answer take 2 iterators @ beginning, increment first 1 once, , second 1 twice. check see if point same object. repeat until 1 incrementing twice either hits first 1 or reaches end.

this algorithm finds circular link in list, not it's complete circle.

pseudo-code (not java, untested -- off top of head)

bool hascircle(list l) {    iterator = l.begin(), j = l.begin();    while (true) {       // increment iterators, if either @ end, you're done, no circle       if (i.hasnext())  = i.next(); else return false;        // second iterator travelling twice fast first       if (j.hasnext())  j = j.next(); else return false;       if (j.hasnext())  j = j.next(); else return false;        // should whatever test shows 2       // iterators pointing @ same place       if (i.getobject() == j.getobject()) {            return true;       }     } } 

Comments

Popular posts from this blog

Delphi Wmi Query on a Remote Machine -