c++algorithmfloyd-cycle-finding

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?


Solution

  • 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();
    }