Floyd的循环寻找算法

我试图在.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 关于这个解决方案,我发现在常规算法中他们只使用一个快速迭代器,但在这里他们使用两个,为什么?     
已邀请:
你发现的代码中的想法似乎很好。两个快速迭代器用于方便(虽然我很积极,这种'方便',比如在
while
循环的条件下放置很多'动作',应该避免)。您可以使用一个变量以更易读的方式重写它:
while (fastNode && fastNode.next()) {
    if (fastNode.next() == slowNode || fastNode.next().next() == slowNode) {
        return true;
    }
    fastNode = fastNode.next().next();
    slowNode = slowNode.next();
}
    
算法是正确的。证明: 没有周期的情况是微不足道的:野兔将找到列表的末尾。 所以,有一个循环,野兔进入它,疯狂地跑来跑去。最终,乌龟到达循环的第一个节点。从这一点开始,两者都必须停留在循环中:它们从节点进入的唯一方式是到下一个节点,最终导致返回到循环的第一个节点。 (绘制列表/图表的图片以说服自己。) 由于野兔移动得更快,它最终会赶上乌龟。根据循环的长度和进入之前遍历的节点数量(无论它们是奇数还是偶数是重要的,因此有四种情况),这可能发生在奇数或偶数步骤之后。这就是为什么兔子应该检查它的当前节点和乌龟存在的下一个节点。 (示例代码使用两个指针来实现这一点,尽管这不是必需的。) 有关更正式的证明,请查看此Wikipedia页面。     
该算法将在链表中找到一个循环。 可以使用一个快节点:
 function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode = startNode;
  while (slowNode && fastNode = fastNode.next() && fastNode = fastNode.next()){
    if (slowNode == fastNode) return true;
    slowNode = slowNode.next();
  }
  return false;
}
    

要回复问题请先登录注册