s c h e m a t i c s : c o o k b o o k

; split-in-halves : list -> (values list list)
;  return two lists of lengths differing with at most one
(define (split-in-halves l)
  (let loop ([front '()]
             [slow  l]
             [fast  l])
    (cond
      [(null? fast)         (values front
                                    slow)]
      [(null? (cdr fast))   (values (cons (car slow) front)
                                    (cdr slow))]
      [else                 (loop (cons (car slow) front)
                                  (cdr slow)
                                  (cddr fast))])))

; split-in-halves! : list -> (values list list)
;  return two lists of lengths differing with at most one;
;  modifies the argument
(define (split-in-halves! l)
  (let loop ([slow (cons 'foo l)]
             [fast (cons 'bar l)])
    (cond
      [(or (null? fast)
           (null? (cdr fast))) (let ([back (cdr slow)])
                                 (set-cdr! slow '())
                                 (values l back))]
      [else                    (loop (cdr slow)
                                     (cddr fast))])))

> (split-in-halves (list 1 2 3 4 5))
(3 2 1)
(4 5)
> (split-in-halves (list 1 2 3 4 5 6))
(3 2 1)
(4 5 6)

> (split-in-halves! (list 1 2 3 4 5))
(1 2 3)
(4 5)
> (split-in-halves! (list 1 2 3 4 5 6))
(1 2 3)
(4 5 6)