We can find the midpoint of a list by keeping two pointers, moving one by two steps and another by one step, O(n).
(defun midpoint (lst)
(let (prev current)
(setq current lst)
(setq prev lst)
(while (and (not (null lst))
(not (null (rest lst))))
(setq lst (rest (rest lst)))
(setq prev current)
(setq current (rest current)) )
prev))
public static Cons midpoint (Cons lst) {
Cons current = (Cons) lst;
Cons prev = current;
while ( lst != null rest(lst) != null) {
lst = (Cons) rest(rest(lst));
prev = current;
current = (Cons) rest(current); };
return prev; }