-
Notifications
You must be signed in to change notification settings - Fork 0
/
3_19.scm
34 lines (30 loc) · 918 Bytes
/
3_19.scm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
(define (append! x y)
(set-cdr! (last-pair x) y)
x)
(define (last-pair x)
(if (null? (cdr x))
x
(last-pair (cdr x))))
(define has-cycle
(let ((acc (list '())))
(lambda (x)
(cond ((eq? (cdr x) '()) #f)
((memq x acc) #t)
(else (begin (append! acc (list x))
(has-cycle (cdr x))))))))
(define (has-cycle-floyd x)
(define (has-cycle-floyd-rec first second)
(cond ((or (null? (cdr first)) (null? (cddr first))
(null? (cdr second))) #f)
((eq? first second) #t)
(else has-cycle-floyd-rec (cddr first) (cdr second))))
(if (and (not (null? x)) (not (null? (cdr x))) (not (null? (cddr x))))
(has-cycle-floyd-rec (cddr x) (cdr x))
#f))
(define (make-cycle x)
(set-cdr! (last-pair x) x)
x)
(define z (make-cycle (list 'a 'b 'c)))
(define a (list 'a 'b 'c))
(has-cycle-floyd a)
(has-cycle z)