c++ - Floyd 循环查找算法中使用的 While 条件

Question

我能够理解 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;
        }

    }

}

Answer 1

考虑一个空链表，其中 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) 的段错误