CareerCup

we don't really use ratio 2:1. We just make one pointer move little bit (+1) faster than other. if we moved the faster pointer any faster, it could jump over slower pointer and we wont be able to detect the loop in 1 pass. By using steps of 1 and 2 we ensure that we catch the loop 1st time faster pointer passes slower one. BTW using 5:6 or (125:126) would work well too. but it doesn't give any additional benefit.

Any combination of speed that we take (F and S) is guaranteed to give result in the same number of cycles as the LCM of F and S. The minimum of that is 2 and hence the ratio 2:1

Say in each step, the fast pointer moves F nodes ahead and the slow pointer moves S nodes. So in each step, the distance between the two pointers increases by F-S.

Say there is a loop starting at the B-th node (B>=1), and the loop size is L >= 1 (self-loop is OK). If it takes N steps to detect the loop, we should have

N >= B and (F - S) * N % L == 0

This is easy to see that

N = L * K / ( F - S )

where K is the smallest number such that L * K >= B and L * K % ( F - S ) == 0.

Then the total cost for detecting a loop can be formulated as

( F + S ) * N = L * K * ( F + S ) / ( F - S )
subject to L * K >= B and L * K % ( F - S ) == 0

Now consider the case when L and F - S are mutually prime and the loop starts at the head of the list. In this case, we need at least K = F - S to satisfy L * K % ( F - S ) == 0. Then the cost becomes

L * ( F + S )

So we should pick the smallest F and S possible to reduce cost. So F = 2 and S = 1 is the best choice.

Suppose the distance of loop entry from the starting point is A, and the loop size is B, and the speed ration of the slow and fast pointers is 1:N.

At A'th step the slow pointer reaches the entry, while the fast pointer is
behide the slow pointer by distance X.

X = (B - ((N - 1) * A) % B)) % B   // note 0<=X<B-1

It will take floor (X / (N - 1)) steps for the fast pointer to catch the slow pointer.

The total cost is

Y = (A + floor(X / (N -1)) * (N + 1)

Obviously

A * (N + 1) <= Y <= (A + floor ((B - 1) / N - 1)) * (N + 1)

Since the lower bound is A * (N + 1), we should make N as small as possible.

For curious readers the upper bound is

(A + floor ((B - 1) / N - 1)) * (N + 1) < (A + 1  + (B-1)/(N-1))*(N+1)
    = (A+1)*(N+1) + (B-1)(1 + 2/(N-1))

With every step the gap between slower and faster pointer increases by 1...So, gap start as 0 and increments by 1 (until say 2, 3, 4, 5) and then it starts decrementing by 1 (say 5,4,3,2,1,0). once we reach 0 we can say that both pointers point to the same number

boolean hasLoop(Node first) {

    if(first == null) // list does not exist..so no loop either.
        return false;

    Node slow, fast; // create two references.

    slow = fast = first; // make both refer to the start of the list.

    while(true) {

        slow = slow.next;          // 1 hop.

        if(fast.next != null)
            fast = fast.next.next; // 2 hops.
        else
            return false;          // next node null => no loop.

        if(slow == null || fast == null) // if either hits null..no loop.
            return false;

        if(slow == fast) // if the two ever meet...we must have a loop.
            return true;
    }
}