此代码用于在单个链表中查找循环,我已从 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.
最佳答案
这是布伦特的循环寻找算法。 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 算法所需的第二个“慢”指针是不切实际的。
关于algorithm - 你能解释一下下面这段在链表中查找循环的代码片段是如何工作的吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50552276/