Floyd's cycle-finding algorithm (Scheme)

From LiteratePrograms

Other implementations: C | Scheme

Floyd's cycle-finding algorithm, also known as the Tortoise and the Hare, detects a cycle in a list by using two iterators, a slow iterator ("tortoise") that walks the list one element at the time, and a fast iterator ("hare") that walks it two at a time. If there is a cycle, at some point the hare will overtake the tortoise; if there is no cycle, the hare gets to the end of the list first.

We need a helper function that operates on two lists: one as used by the slow iterator and one as used by the fast iterator.

<<has-cycle-h>>=
(define (has-cycle-h slow-ls fast-ls)
  (cond
   [(null? fast-ls) #f]
   [(null? (cdr fast-ls)) #f]
   [(eq? (car slow-ls) (car fast-ls)) #t]
   [else (has-cycle-h (cdr slow-ls) (cddr fast-ls))]))

Given this helper, the cycle detector needs to simply call the helper with both lists set to the list to be checked.

<<cycle-finder.scm>>=
has-cycle-h
(define (has-cycle? ls)
  (cond
    [(null? ls) #f]
    [else (has-cycle-h ls (cdr ls))]))

Download code