Floyd的循环寻找算法

Question

我试图在.NET上用C++找到这个算法,但不能,我找到了这个:

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

但似乎不对,或者我错了？我怎么能真正证明我的野兔最终会遇到乌龟？提前感谢任何解释它是如何工作的proof

EDITED

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

Answer 1

您找到的代码中的想法似乎不错。使用两个快速迭代器是为了方便（尽管我确信这种“方便”，比如在循环条件下放置大量“动作” while，应该避免）。您可以使用一个变量以更易读的方式重写它：

while (fastNode && fastNode.next()) {
    if (fastNode.next() == slowNode || fastNode.next().next() == slowNode) {
        return true;
    }
    fastNode = fastNode.next().next();
    slowNode = slowNode.next();
}