Floyd's cycle-finding algorithm (Scheme)
- 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>>= (define (has-cycle? ls) (cond [(null? ls) #f] [else (has-cycle-h ls (cdr ls))]))