Get the middle elements from List in scheme

问题:

I'm new to scheme , can someone please give me ideas on how to get , "the middle element from a list?"

回答1:

Here's my solution. It's based on a tortoise-and-hare algorithm (which is used in any kind of list traversal where you need to detect circular lists), so it doesn't do any more work than a sane list traversal has to do anyway. :-)

(define (middle-elements lst)
  (if (null? lst) '()
      (let loop ((tortoise lst)
                 (hare (cdr lst)))
        (cond ((eq? tortoise hare) #f)
              ((null? hare) (list (car tortoise)))
              ((null? (cdr hare)) (list (car tortoise) (cadr tortoise)))
              (else (loop (cdr tortoise) (cddr hare)))))))

It covers the following cases:

• If given an empty list, returns an empty list.
• If given a list with an odd number of elements, returns a singleton list with the middle element.
• If given a list with an even number of elements, returns a list with the two middle elements.
• If given a circular list, returns #f.
• If given an improper list (including a non-list), summons nasal demons.