c++ - 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

已编辑

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

Answer 1

您发现的代码中的想法似乎不错。为了方便起见，使用了两个快速迭代器(尽管我很肯定这种“方便”，比如在 while 循环的条件下放置大量“ Action ”，应该避免)。您可以使用一个变量以更具可读性的方式重写它:

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