335. Forward Chain Addition
Two huge non-negative numbers are stored digit by digit in chains, this time with the most significant digit first, exactly as you would write them. So the chain 2, 0, 4 stands for 204. Each node holds one digit from 0 to 9, and the numbers are too long for a built-in integer type.
Given the heads a and b, add the two numbers and return the sum as a chain, again most significant digit first. The inputs may contain extra zeros at the front, but the result must be in standard form: no unnecessary leading zeros, and zero itself is the single node 0. You may not reverse the input chains in place, and each has between 1 and 100,000 nodes.
Example 1
- Input:
- a = [4,9,7], b = [3,5]
- Output:
- [5,3,2]
- Explanation:
497 + 35 = 532, written most significant first as 5, 3, 2.
Example 2
- Input:
- a = [9,9,9,9], b = [6]
- Output:
- [1,0,0,0,5]
- Explanation:
9999 + 6 = 10005, producing a new leading digit: 1, 0, 0, 0, 5.
Constraints
1 ≤ length of each chain ≤ 105
0 ≤ node value ≤ 9
The first node is the most significant digit.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n + m)