Examine a list for cycles
I can not express it in Lisp, but the idea is as follows:

use two pointers, at start point both to the list head. Then, increment one pointer by 1, and another by 2. If you detect two equal objects eventually, it means that list has a loop. In pseudo-code:

P0 = head;
P1 = head;
while(P0 != null and P1 != null) // Detect end of the list
  P0 = next(P0);
  P1 = next(next(P1));
  if ( *P0 == *P1 ) signal loop detected
end while


Of course, the list objects should be distinct and comparable, and next function must be correct.

Proof is not complicated. First, consider a case of "pure" loop when tail connected to head.

At step n (n'th iteration of the while loop in the code), P0 is at item (n mod N), and P1 is at item (2n mod N), which are equal if N is finite and n mod N == 0, or simply n = N

If the list has loop that starts somewhere inside, one can show that after some iterations the case will be reduced to the previous one.

Hope this helps. You can learn more about Cycle detection on Wikipedia.