Determining if a linked list loops using only two pointers (idea) by zra

Here's a rough sketch of a proof:

Assume that we have a list with transient(non-looping part) of length T>=0 and period(looping part) of length P>1. Send two pointers down the list. One will advance j₁ nodes at a time, the other will advance j₂!=j₁ nodes at a time. So, at some smallest time t₀, both pointers will be in the loop, if there is one. The position of a pointer at t₀ will depend on T and j. For the moment lets just call the positions of our pointers at t₀, x₁ and x₂. So, the positions of the pointers in the loop are given by:

(j₁*t+x₁) mod P and (j₂*t+x₂) mod P

For this technique to work, we need the positions to be equal at some time t>t₀. So,

(j₁*t+x₁) = (j₂*t+x₂) mod P =>

(j₁*t - j₂*t + x₁ - x₂) = 0 mod P =>

((j₁-j₂)t+(x₁-x₂))/P = n for some integer n>0 =>

t = nP/(j₁-j₂) + (x₁-x₂)/(j₁-j₂).

So, if j₁=2 and j₂=1, as above, t is obviously an integer for any P and T, which was what we wanted.

never use variable arguments in C++	Reversing a linked list	hard interview questions	Why the college fraternity and sorority system is ridiculous
GTKY	linked list	Porn In Hamlet	The principles of nuclear weapon safety and meeting girls are remarkably similar
binary search tree	Firestarter	Storing a doubly-linked list using just a single pointer field	pointer
OpenGL	Tip of the Day	iterate	algorithm
cross-linked list	Which was what we wanted	ELOOP	gcd
Rational Algorithm	list processing	genetic algorithm	The light I never node