Finding a loop in a linked list
I have been reading through the excellent SICP recently which has been an enlightening experience. The book takes a unique approach to the introductory programming textbook focusing not merely on introducing various basic constructs but on the computer language as a “novel formal medium for expressing ideas about methodology”.
Chapter three introduces assignment along with set-car! and set-cdr! for the modification of lists. This leads on to an interesting discussion of how lists are structured in memory and the possibility of creating a looped linked list with the procedures:
(define (last-pair x) (if (null? (cdr x)) x (last-pair (cdr x)))) (define (make-cycle x) (set-cdr! (last-pair x) x) x)
As you can see make-cycle connects the end of x to the start forming a loop. Exercise 3.18 asks the reader to define a procedure which will determine whether a list contains a cycle or not. This can easily be achieved using eq? and waiting until we reach a null or visit a node twice. The problem is that this seems to require some auxiliary data structure or temporary modification of the original list.
Exercise 3.19 pushes us further and asks for an algorithm which runs in constant space. A possible solution would be:
(define (cyclic? x) (define (fast-adv x) (if (null? (cdr x)) '() (cddr x))) (define (cyclic-check slow fast) (cond ((null? fast) false) ((eq? fast slow) true) (else (cyclic-check (cdr slow) (fast-adv fast))))) (if (null? x) false (cyclic-check x (fast-adv x))))
Unfortunately my Scheme isn’t great and there is a little bit of redundancy in my expression of the algorithm but it achieves the goal of finding a loop using constant space. This works by having two pairs: one which advances normally with cdr and one which advances two at a time using fast-adv. If there is a loop in our list the slow object will eventually catch up with the fast one, otherwise we will reach the end. If you aren’t familiar with functional languages you may be wondering about the recursion in the previous procedure but since it is tail recursive it is in fact an iterative process. This algorithm is due to Robert W Floyd.
Wikipedia has an interesting article on cycle detection in terms of iterated functions which includes a discussion of Floyd’s algorithm.