algorithm - 你能解释一下下面这段在链表中查找循环的代码片段是如何工作的吗？

Question

此代码用于在单个链表中查找循环，我已从 http://blog.ostermiller.org/find-loop-singly-linked-list 了解了它但我无法理解为什么代码是这样写的。

此解决方案由 Stephen Ostermiller 设计，并由 Daniel Martin 证明为 O(n)。

function boolean hasLoop(Node startNode){
  Node currentNode = startNode;
  Node checkNode = null;
  int since = 0;
  int sinceScale = 2;
  do {
    if (checkNode == currentNode) return true;
    if (since >= sinceScale){
        checkNode = currentNode;
        since = 0;
        sinceScale = 2*sinceScale;
    }
    since++;
  } while (currentNode = currentNode.next());
  return false;
}

最后也提到了这一点:

This solution is O(n) because sinceScale grows linearly with the number of calls to next(). Once sinceScale is greater than the size of the loop, another n calls to next() may be required to detect the loop.

Answer 1

这是布伦特的循环寻找算法。 https://en.wikipedia.org/wiki/Cycle_detection#Brent%27s_algorithm

在大多数情况下，我比 Floyd 算法更喜欢它。它确实在 O(N) 时间内有效:

• 将 currentNode 放入列表的循环部分需要 O(N) 步。
• 然后它将执行 O(N) 更多 步，直到 since == sinceScale，并且 checkNode 设置为 currentNode
• 从那时起，checkNode 和currentNode 都在循环中。随着 sinceScale 变大，重置 checkNode 的频率会降低。当它足够大时，checkNode 将保持不变，直到 currentNode 一直绕着循环并检测到循环。每次将 sinceScale 缩放 2 确保这也在 O(N) 中发生。

对于在链表中查找循环，Floyd 算法或 Brent 算法都可以正常工作，但 Brent 算法在很多现实生活中更方便，因为从当前状态到下一个状态的代价很高，而且它会是移动 Floyd 算法所需的第二个“慢”指针是不切实际的。