Add Two Numbers Represented as Linked Lists

Problem: Given two non-negative numbers represented as linked lists (each node holding a single digit), add the two numbers and return the sum as a linked list.

Constraints: Digits may be stored in forward order (most significant digit first) or reverse order (least significant digit first) - clarify with the interviewer as this changes the approach.

Example: 342 + 465 = 807, represented as lists.

Approach: If least-significant-digit-first, traverse both lists simultaneously, adding corresponding digits plus carry-over, creating result nodes as you go, and appending a final carry node if needed - O(n) time. If most-significant-digit-first, either reverse both lists first (then apply the above) or use recursion to add from the tail back towards the head, propagating carries backward.