java - What is an efficient algorithm to find whether a singly linked list is circular/cyclic or not? -
this question has answer here:
- how detect loop in linked list? 21 answers
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:
1
→ 3
→ 5
→ 71
→ 45
→ 7
→ 5
, 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
Post a Comment