Add Reversed Digit Chains
MediumLinked List
Problem
A bank stores very large balances as linked lists of decimal digits, least significant digit first: the number 942 is stored as [2, 4, 9].
Given two such lists a and b (no leading zeros except the number 0 itself), return their sum in the same format.
Example 1
- Input:
- a = [2, 4, 9], b = [5, 6, 4]
- Output:
- [7, 0, 4, 1]
942 + 465 = 1407, stored as [7, 0, 4, 1].
Example 2
- Input:
- a = [0], b = [0]
- Output:
- [0]
Constraints
- 1 ≤ nodes in each list ≤ 1000
- 0 ≤ node.val ≤ 9
- Neither number has leading zeros, except the number 0.
Hint
Show the first hint
Converting to integers overflows in most languages at 1000 digits. Do it digit by digit.
Walkthrough
How to approach it
01Clarify before coding
- Which end is the ones digit? The head: digits are stored in reverse.
- Can the lists have different lengths? Yes; a missing digit counts as 0.
- Can the result be longer than both inputs? Yes, by one digit from a final carry.
02Brute force
Turn each list into an integer, add them, and turn the sum back into a list.
Cost: O(n) digit operations with big integers, but it overflows 64-bit integers past 19 digits in most languages, so it is not a general answer.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.