 Solution

Convert the tail first and apply the reciprocal identity. Two output parameters hold the rational number's numerator and denominator.The singleton case is immediate. If the recursive call returns the tail as $u/v$, then $u,v>0$ because every tail head is positive. The full value isStructural induction on the finite nonempty linked list proves correctness, and the denominator is always positive even if the first head is negative. If the tail pair is coprime, then $\gcd (xu+v,u)=\gcd (v,u)=1$; the base pair $(x,1)$ is coprime, so the result is in lowest terms. Return (head*u+v,u) after converting the tail, using linear node-processing time and linear recursive stack space.