我能够理解 Floyd 循环查找算法工作原理的基本原理。我唯一无法理解的是 while 循环条件,如下所示:
while(slow && fast && fast->next){
slow = slow->next;
/*Moving fast pointer two steps at a time */
fast = fast->next->next;
if(slow == fast){
loop_found = 1;
break;
}
}
因为 fast->next
将移动得最快并且首先变为 NULL。为什么我们不能将 fast->next
放在 while
循环中。这样做时我是否会遗漏某些边界条件?
while(fast->next) instead of `while(slow && fast && fast->next)`
我写了下面的代码,它对偶数和奇数有序线性链表都工作得很好。那么,我们是否需要在 while 循环中使用 fastPtr
条件来进行 空链表检查
。请指教。
void linklist::detect()
{
node * fastPtr = new node;
node * slwPtr = new node;
slwPtr = head;
fastPtr = head;
while (/*slwPtr!=NULL && fastPtr!=NULL &&*/ fastPtr->next!=NULL)
{
fastPtr = fastPtr->next->next;
slwPtr = slwPtr->next;
if (fastPtr == slwPtr)
{
cout << "Loop Detected\n";
break;
}
}
}
最佳答案
考虑一个空链表,其中 slow 和 fast 为 null,我们需要适当的 null 检查。由于您引用的内容,我们可以避免缓慢的 null 检查。
while(fast && fast->next) //This should do.
考虑到您的解决方案,我们将因取消引用 Null 指针而导致 Segmentation Fault
。
添加 while 检查以检查节点是否在这些场景中不为 NULL:
- 空链表。
fast = NULL
。 - 线性链表,即没有循环(2 个节点)。
考虑一个链表 1->2->NULL 第一次迭代:fast = 1 并被修改为 fast =NULL 第二次迭代:while(fast->next) 的段错误
关于c++ - Floyd 循环查找算法中使用的 While 条件,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27647349/