Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Floyd's cycle-finding algorithm

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

EDITED

About this solution, I found that in regular algorithm they use only one fast iterator but here they use two, why?

like image 225
rookie Avatar asked Oct 07 '10 10:10

rookie


1 Answers

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();
}
like image 147
Nikita Rybak Avatar answered Sep 24 '22 16:09

Nikita Rybak