0

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

该解决方案由 Stephen Osteriller 设计，并由 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;
}

最后也提到了这一点：

这个解决方案是 O(n)，因为 sinceScale 随着对 next() 的调用次数线性增长。一旦 sinceScale 大于循环的大小，可能需要再调用一次 next() 来检测循环。

4

1 回答 1

1

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

在大多数情况下，我比弗洛伊德算法更喜欢它。它确实在 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 算法需要的第二个“慢”指针。

于 2018-05-27T14:44:47.940 回答