I am writing code to find the sum of two numbers, each represented by list whose nodes contain decimal digits in reverse order. E.g.,
sum [2; 4; 3] [5; 6; 4] = [7; 0; 8] since 342 + 465 = 807.
Now, if the digits were stored in non-reverse order, then the following would work in O(n) time:
let sum l1 l2 = let rec loop carry result l1 l2 = match l1, l2 with | ,  -> result | , h::t | h::t,  -> let sum = h + carry in let carry = sum / 10 in loop carry ((sum mod 10)::result)  t | h1::t1, h2::t2 -> let sum = h1 + h2 + carry in let carry = sum / 10 in loop carry ((sum mod 10)::result) t1 t2 in loop 0  l1 l2
If I were to change
(sum mod 10)::result to
result @ [sum mod 10] to get the result in reverse order, then the asymptotic running time would be O(n^2), due to the asymptotically linear time of the append operation.
In imperative languages, the pointer to the next element could be saved, removing the need to walk the list with each append operation.
I am new to OCaml and am wondering if there is a way I can write this in O(n) time.