# Examine a list for cycles

From SICP:

Exercise 3.18. Write a procedure that examines a list and determines whether it contains a cycle, that is, whether a program that tried to find the end of the list by taking successive cdrs would go into an infinite loop. Exercise 3.13 constructed such lists.

I wrote the following (revised) solution:

(define (has-cycle? l)
(define (rec nodes-visited remains)
(define (leaf? node) (not (pair? node)))
(define (have-seen? node)
(define (rec rest)
(if (null? rest) #f
(or (eq? (car rest) node)
(rec (cdr rest)))))
(rec nodes-visited))
(cond
((leaf? remains) #f)
((have-seen? remains) #t)
(else
(or (rec (cons remains nodes-visited) (car remains))
(rec (cons remains nodes-visited) (cdr remains))))))
(rec '() l))

(define (last-pair x)
(if (null? (cdr x))
x
(last-pair (cdr x))))

(define a '(a b c))
(has-cycle? a)
(set-car! (last-pair a) a)
a
(has-cycle? a)

(define b '(a b c))
(set-car! b (last-pair b))
b
(has-cycle? b)

(define c '(a b c d))

(set-car! (cddr c) (cdr c))
c
(has-cycle? c)

(define d (cons 'z a))
d
(has-cycle? d)

(define e '(a b c d e))
e
(has-cycle? e)

1. How can it be improved?

Exercise 3.19. Redo exercise 3.18 using an algorithm that takes only a constant amount of space. (This requires a very clever idea.)

1. I'm not sure how to fulfill this requirement so far.
• Have you tried this on a cyclic list? I did, and it goes into an infinite loop. Feb 7 '12 at 2:56
• What list did you use? (define a... above makes a cyclic list and it returned ok for me. Feb 7 '12 at 12:10
• Try it with a cyclic list where the cycle doesn't begin with the first element, i.e. (cons 'z a) where a is the same as in your example Feb 7 '12 at 13:09
• You're right - I'll need to think about this a bit to see if I can make it work. Feb 8 '12 at 14:32
• Why not just replace the code on top with the updated code, leaving a note that the code is updated? Those who are then interested in seing the changes can see the edit history. Feb 8 '12 at 18:50

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;
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.