(defun xons (x y)
  (labels ((fwd (x y)
             (setf (fdefinition 'xons) #'bwd)
             (cons x y))
           (bwd (x y)
             (setf (fdefinition 'xons) #'fwd)
             (cons y x)))
    (fwd x y)))

(mapcar 'xons '(1 2 3 4 5 6) '(a b c d e f))
;=> ((A . 1) (B . 2) (C . 3) (D . 4) (E . 5) (F . 6)) ; first time
;=> ((1 . A) (2 . B) (3 . C) (4 . D) (5 . E) (6 . F)) ; second time

(reduce 'xons '(1 2 3 4 5 6) :initial-value '())
;=> (1 2 3 4 5 6)                            ; first time
;=> ((((((NIL . 1) . 2) . 3) . 4) . 5) . 6)  ; second time