Proof of the 2 pointer method for finding a linked list loop The linked list with a loop problem is classical - "how do you detect that a linked list has a loop" ? The "creative" solution to this is to use 2 pointers, one moving at a speed of 1 and the second one at the speed of 2. If the two pointers meet then there is a loop. 
How do you prove this mathematically and more importantly how do you generalize? For example, will having the first pointer at a speed of 2 and the second at the speed of 3 still work?
For those without a background in CS, a linked list is a collection of nodes, each node has a link to the next one. So you can only go forward. 
 A: If there is a loop (of $n$ nodes), then once a pointer has entered the loop it will remain there forever; so we can move forward in time until both pointers are in the loop. From here on the pointers can be represented by integers modulo $n$ with initial values $a$ and $b$. The condition for them to meet after $t$ steps is then
$a + t \equiv b + 2t \text{ mod }n$
which has solution $t = a - b \text{ mod }n$.
This will work so long as the difference between the speeds shares no prime factors with $n$.
A: HINT: The distance between pointers is increased by $1$ each step. The single restriction on speeds is that their diference should be coprime with the loop's length.
A: Say, there are $l$ elements before the cycle, and the cycle has $n$ elements. We will use two references $R_p$ and $R_q$ which take $p$ and $q$ steps in each iteration; $p > q$. In the Floyd's algorithm, $p = 2, q = 1$.
For any $i$, we can find the "index" (position) at which we reach after taking $i$ steps from the head. So index ranges from 0 to $l+n-1$. We can prove that for any $i \ge l$, the index is:
$l + (i-l) \bmod n$
So, after $s$ iterations, $R_p$ and $R_q$ will meet iff:
(assuming $qs \ge l$ and so $ps \ge l$ also)
$l + (ps − l) \bmod n = l + (qs − l) \bmod n$
$\Leftrightarrow ((p − q)s) \bmod n = 0$
$\Leftrightarrow (p − q)s = \text{a multiple of } n$
For any given $p$ and $q$ with $p > q$, we can find $s$ satisfying above (e.g. $s$ = a multiple of $n$). So we can conclude that $R_p$ and $R_q$ will always meet after some number of iterations.
You may refer this article (written by me) for more background; section "Other Step-Counts for References".
