1

So I recently encountered the algorithm to determine whether a cycle exists in a linked list. The codes are as follows:

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;
}

When trying to prove the correctness of this algorithm, I come up with an idea: Suppose the perimeter of the cycle is "a", the time elapsed before two pointers meet is "t". Since the speed of the "fast" node moves twice as fast as the "slow" node, we can get the mathematical relation:

2t mod a = t mod a

Now "a" is a constant represents perimeter, and "t" could be 1,2,3.... Then, how do I prove that no matter what value "a" is, we can always find a "t" such that the above equation is solvable?

Zhengyang Fang
  • 11
  • 1

2 Answers2

0

You are on the right track! Hint: what happens to your formula after a iterations?

Aasmund Eldhuset
  • 37,289
  • 4
  • 68
  • 81
0

Assuming both pointer starts at same point within the cycle (and this does not count as meeting)

2t = t (a)

=> 2t - t = 0 (a)

=> t = 0 (a)

which means at t = a*k, both pointers will meet at starting point after elapsed time is multiples of the cycle length.

It is true for all a >= 2, because when time equals to k*a for all k>1, the slow pointer exactly runs k cycles long, while the fast pointer runs twice faster, so it runs 2k cycles long, still they meet at the same point which is the starting point.

shole
  • 4,046
  • 2
  • 29
  • 69