Add Two Numbers

Problem

You are given two non-empty singly linked lists, each representing a non-negative integer with its digits stored in reverse order (the head holds the least significant digit). Each node holds a single digit 0-9. Add the two numbers and return the sum as a linked list in the same reversed-digit format. Neither input has leading zeros except the number 0 itself.

• Each list has between 1 and 500 nodes.
• Every node holds a single digit, 0 through 9.

Examples

• l1 = 6 -> 1 -> 7 (716), l2 = 5 -> 9 -> 2 (295) → 1 -> 1 -> 0 -> 1 (1011). Carries ripple through every position and one more digit is produced.
• l1 = 4, l2 = 0 → 4. Adding zero returns the other number.
• l1 = 8 -> 9 -> 9 -> 9 -> 9 (99998), l2 = 3 -> 1 (13) → 1 -> 1 -> 0 -> 0 -> 0 -> 1 (100011). The shorter list runs out early, but the carry keeps going.

Hints

1. The lists are already in the order you would add digits by hand: least significant first.
2. At each position, the digit is (a + b + carry) % 10 and the new carry is (a + b + carry) // 10. What happens when one list is shorter?
3. Loop while either list has nodes or the carry is non-zero, treating a missing node as 0.