c - 如果我们在链表中查找循环时改变慢指针和快指针的跳数会怎样？

Question

要找到链表中的循环，我们只需使用两个指针慢速和快速即可。

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个节点，会有什么影响……

我在代码中尝试过这个，但每次都得到正确的结果。有人可以解释一下吗？另外，我立即想到的另一件事是，我们可以通过某种特定的慢指针和快指针选择进入无限循环，但找不到一个。

Answer 1

Change in number of hopes will only diminish cycle finding process. It wouldn't put you in infinite loop.

节点数要么是奇数，要么是偶数。所以

Case A : For odd number of nodes (3 or 5 nodes for example)
Case B : For even number of nodes (2 or 4nodes for example)

参见测试示例场景:通用解决方案是:GCD(慢速运动，快运动)将是循环内节点在时间上胶体的点。

1. (偶数，奇数)慢速移动 2，快移动 3:在情况 A 和 B 中都会被捕获。因为在情况 A 中，快速将继续返回到所选节点(每隔三个节点)，而慢会交替变化。

2. (奇数，偶数)慢速移动 3，快移动 4:在情况 A 和 B 中都会被捕获。因为在情况 A 中，快速将继续返回到每四个节点，并在每三个节点处慢速。这样他们应该会在循环中的第 12 个位置上发生碰撞。

3. (odd, odd)慢移动1，快移动3:在情况A和B中都被捕获。两者的GCD都是3，所以他们应该在即将到来的第三个节点相遇。

4. (偶，偶)慢移动2，快移动4:在情况A和B中都被捕获。道理相同。