如果在链表中查找循环时更改慢指针和快指针的跳数会发生什么？

Question

为了在链表中找到一个循环，我们只需使用两个指针slow和fast。

slow = head->next;
fast = head->next->next;

    while(slow != fast)
    {
        slow = head->next;
        fast = head->next->next;
        if(!slow || !fast)
        {
            cout<<"   No Loop ";
            break;
        }
    }

我们可以通过这种方法找到链表中的循环。 那么，如果我让慢指针跳2个节点，快指针跳3个节点，或者慢指针跳3个节点，快指针跳4个节点，会有什么后果......

我在我的代码中尝试了这个方法，但每次都得到正确的结果。 有没有人能够阐述一下？另外，我立刻想到的另一件事是，我们可以通过某些特定的慢指针和快指针选择进入无限循环，但是找不到。

- instance

---

请注意，您的伪代码是一个无限循环，因为它总是从“head”开始，并且从不处理给定列表不是循环的情况（没有列表结尾检查）。 - Frerich Raabe

@FrerichRaabev...我修改了伪代码...现在请给我答案。 - instance

慢指针和快指针仍然始终从头开始，因此在每次迭代中它们具有相同的值，因此仍然是无限循环。此外，如果 head->next 为空，尝试获取 fast 的值时会出现空指针引用崩溃。 - Darth Hunterix

@DarthHunterix ....哦，我刚刚粗略地写了这段代码...我不想深入讨论代码的正确性...我只是想理解这个概念...将慢速和快速更改跳数是否会产生负面影响。 - instance

Answer 1

改变节点数只会减少循环查找的过程，不会使你陷入无限循环。
节点数量为奇数或偶数，因此：
情况A：节点数为奇数（例如3或5个节点）
情况B：节点数为偶数（例如2或4个节点）
参见测试样本场景：广义解是：慢指针和快指针的移动的最大公约数将是节点在时间内重合的点。
1. (偶数，奇数) 慢指针每次移动2个节点，快指针每次移动3个节点：在情况A和B中都被捕获。在情况A中，快指针将继续回到所选节点（每三个节点一次），而慢指针将交替更改。
2. (奇数，偶数) 慢指针每次移动3个节点，快指针每次移动4个节点：在情况A和B中都被捕获。在情况A中，快指针将继续返回每四个节点，而慢指针将在每三个节点处。这样，它们应该在循环中的第12个位置相遇。
3. (奇数，奇数) 慢指针每次移动1个节点，快指针每次移动3个节点：在情况A和B中都被捕获。它们的最大公约数是3，因此它们应该在开始后的第三个节点相遇。
4. (偶数，偶数) 慢指针每次移动2个节点，快指针每次移动4个节点：在情况A和B中都被捕获。同样的原因。

- user3721704