; must add Ulrich's solution to this file! 1. The "tortoise and hare" solution is very elegant and also finite storage. Just kave two pointers and send them stepping down the list: one steps one cdr at a time, the other steps two at a time. After every step, compare them. If they are ever equal, then it's cyclic. Why does this work? Actually, any two relatively prime numbers will do. If it's cyclic, they're bound to land on the same spot eventually. If not, the first one will reach the end of the list and that's that. I don't know which is supposed to be the tortoise and which is supposed to be the hare, though. Oh well. 2. Here is another solution, given in Scheme code. It is not, strictly speaking, finite storage, since it returns the length of the cycle (which could, after all, be really really big), but in practical terms it is constant space. And anyway, who could have a list longer than their address space allows? This is polynomial time, however. (define make-cyclic-list ; takes n and lst, and makes the last cdr in lst point to the nth cell ; in lst, starting from 0. So the cycle will be of length: ; (- (length lst) n). Everything starts from 0. (lambda (n lst) (let ((head lst)) (let loop ((n n) (lst lst) (head head)) (cond ((null? (cdr lst)) (set-cdr! lst head)) ((zero? n) (loop 0 (cdr lst) head)) (#t (loop (1- n) (cdr lst) (cdr head)))))) lst)) (define cyclic? ; If lst is cyclic, return the length of the cycle, else #f ; The shortest possible cycle length is 0, of course. ; This does not tell you anything about the length of the non-cyclic ; part of the list. (lambda (lst) (let loop ((interval 0) (count 0) (deja '()) (here lst)) (cond ((null? here) #f) ((eq? deja here) count) ((equal? interval count) (loop (1+ interval) 0 here (cdr here))) (else (loop interval (1+ count) deja (cdr here))))))) 3. Ulrich's solution: