>>848

(* OCaml *)
let f =
let rec g c l = function
| [] -> c l
| hd::tl ->
let h = function
| [] -> assert false
| hd2::tl2 -> (hd2, hd)::(c tl2)
in g h l tl
in g (fun _ -> [])

のほうが良くない？
「与えられた二つのリスト以外のリストを使ってはならない」という条件が曖昧だけど
途中でペアを返すのは微妙かと。
これだと末尾再帰になるし (やることは変わらんので実行速度も変わらんかも知れないけど) 。

>>848 が間違いだとはいわないけどね。

大して自信があって言ってるわけではないです。
この発言に間違い (やそれに準ずるもの) の指摘は
勉強になるので歓迎です。