确定链表中是否存在循环的算法

Question

所以我最近遇到了确定链表中是否存在循环的算法。代码如下:

public boolean hasCycle(ListNode head) {
    if (head == null) {
        return false;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null) {
        if (fast.next == null) {
            return false;
        }
        if (fast.next == slow) {
            return true;
        }
        fast = fast.next.next;
        slow = slow.next;
    }
    return false;
}

在试图证明这个算法的正确性时，我想到了一个想法:假设周期的周长为a，则两个指针相遇的时间为t。由于"快"节点的移动速度是"慢"节点的两倍，我们可以得到数学关系:

2t mod a = t mod a

现在"a"是一个代表周长的常数，"t"可以是1,2,3....那么，我如何证明不管a是多少，我们总能找到一个t，使得上面的方程是可解的呢?

Answer 1

你做对了!提示:在和迭代之后，公式会发生什么?

Answer 2

假设两个指针在循环内的同一点开始(这不算作相遇)

2t = t (a)

=> 2t - t = 0 (a)

=> t = 0 (a)

表示在t = a*k处，经过的时间是循环长度的倍数后，两个指针将在起点相遇。

对于所有a >= 2都是如此，因为对于所有k>1，当时间等于k*a时，慢指针正好运行了k个周期，而快指针运行了两倍，所以它运行了2k个周期，它们仍然在同一点相遇，即起点