Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
41 lines (37 sloc) 1.27 KB

本题是一道经典的面试题,解法也比较有名——Floyd's cycle-finding算法,感兴趣的可以去 wiki 上的解释。

核心思路就是设置两个指针,一个一次走一步,另一个一次走两步,如果两个指针在某时刻相等,则说明该表有环存在。

(define (hasCircle? lst) 
   (define (safe-cdr l) 
     (if (pair? l) 
         (cdr l) 
         '())) 
   (define (iter slow fast) 
     (cond ((not (pair? slow)) #f) 
           ((not (pair? fast)) #f) 
           ((eq? slow fast) #t)
           (else (iter (safe-cdr slow) (safe-cdr (safe-cdr fast)))))) 
   (iter (safe-cdr lst) (safe-cdr (safe-cdr lst))))

(define p3 (cons 'c nil))
(define p2 (cons 'b p3))
(define p1 (cons 'a p2))
(set-cdr! (cddr p1) p1)
(hasCircle? p1)
;Value: #t

我第一次写错了,为了加深大家的理解,我把我错误的代码贴出来,大家可以看看是那里的问题。

; 这是一个错误的版本
(define (hasCircle? l)
  (if (null? l)
    #f
    (let ((slow (cdr l)))
      (if (null? slow)
        #f
        (let ((fast (cdr slow)))
          (if (null? fast)
            #f
            (if (eq? fast slow)
              #t
              (hasCircle? slow))))))))