Two non-negative integers are stored as singly linked lists of decimal digits with the least significant digit first, so 2 -> 4 -> 3 represents 342. Given the heads a and b of two such lists, return a new list in the same format holding their sum. An empty list represents 0.
Examples
Input: a = 2 -> 4 -> 3, b = 5 -> 6 -> 4
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807
Input: a = 9 -> 9, b = 1
Output: 0 -> 0 -> 1
Explanation: 99 + 1 = 100
Constraints
0 <= len(a), len(b) <= 10**4, at least one list is non-empty- Each value is a digit
0..9; there are no leading zeros except the number 0 itself - Target: O(max(len(a), len(b))) time; do not convert the whole number to a Python int
Goals
- Walk two lists of different lengths together
- Propagate a carry, including a final extra digit