Add two numbers (linked list)

Problem Two non-empty linked lists store non-negative integers with digits in REVERSE order. Add them, returning the sum as a same-format list.

Input / Output

• Input: heads l1, l2. Output: head of sum list.

Constraints

• Up to 100 digits each — numbers exceed all primitive types; digit-by-digit is mandatory, not optional.

Example

• 2→4→3 + 5→6→4 → 7→0→8 (342 + 465 = 807).

Expected approach

• Simultaneous walk with carry: digit = (a + b + carry) % 10, carry = /10; dummy head collects output; continue while either list OR carry remains (the trailing-carry 5+5=10 case is the classic miss). O(max(m,n))/O(1) extra. Follow-on: digits in FORWARD order (LC 445) — reverse first, or stacks, or recursion; asked often enough to prepare.