弗洛伊德的循环查找算法 [英] Floyd's cycle-finding algorithm

问题描述

我试图找到这个算法的C ++ .NET中却不能，我发现这一个：

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;
}

但似乎并没有是正确的，还是我错了？我怎样才能真正证明我的兔子会遇到乌龟在结束了吗？感谢您事先的任何解释，究竟它的工作原理和证明

关于本解决方案，我发现，在常规的算法，他们只用一个快速的迭代器，但在这里，他们用两个，为什么呢？

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

推荐答案

在$ C $的想法c您发现似乎罚款。两个快速迭代器用于方便（虽然我敢肯定这样那样的'方便'，就像把大量的动作中的的条件，而循环，应该是避免的）。你可以用一个变量重写它更可读的方式：

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

这篇关于弗洛伊德的循环查找算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！