I'm trying to find this algorithm on C++ in .NET but can't, I found this one:
// Best solution
function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
if (slowNode == fastNode1 || slowNode == fastNode2) return true;
slowNode = slowNode.next();
}
return false;
}
but doesn't seem to be right, or am I wrong? How can I actually prove that my hare will meet tortoise at the end? Thanks in advance for any explanation how exactly does it work and proof
About this solution, I found that in regular algorithm they use only one fast iterator but here they use two, why?
The idea in the code you've found seems fine. Two fast iterators are used for convenience (although I'm positive such kind of 'convenience', like putting a lot of 'action' in the condition of while
loop, should be avoided). You can rewrite it in more readable way with one variable:
while (fastNode && fastNode.next()) {
if (fastNode.next() == slowNode || fastNode.next().next() == slowNode) {
return true;
}
fastNode = fastNode.next().next();
slowNode = slowNode.next();
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With