您能否解释一下以下用于在链表中查找循环的代码片段如何工作?

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

最后还提到了这一点：

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

Answer 1

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

在大多数情况下，我比弗洛伊德的算法更喜欢它。 它确实在O(N(时间内工作：

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

为了在链表中查找循环，无论是弗洛伊德算法还是布伦特算法都可以正常工作，但是布伦特算法在很多现实生活中更方便，因为从当前状态到下一个状态的成本很高，并且移动弗洛伊德算法所需的第二个"慢"指针是不切实际的。