判断链表是否存在环路的算法

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

您走在正确的轨道上!提示:a 次迭代后您的公式会发生什么情况？