Add Two Numbers
Two numbers are stored as linked lists with one digit per node , written backwards : the head is the ones digit. Add the two numbers and return the sum in the same backwards form. The function takes two plain arrays of digits, builds the lists inside, and returns a plain array of digits. Backwards is helpful here, because addition on paper also starts at the ones column. Walk both lists together, add the two digits plus the carry , keep the last digit of that sum, and pass the rest on to the next column.
Constraints
- Each list has between 1 and 100 nodes
- Every node holds a single digit from 0 to 9
- Neither number has a leading zero, except the number 0 itself
- The digits are stored with the ones digit first
Example
Input
digitsA = [2, 4, 3], digitsB = [5, 6, 4]Output
[7, 0, 8]Explanation Backwards, [2, 4, 3] is 342 and [5, 6, 4] is 465. 342 + 465 = 807, which written backwards is [7, 0, 8].
In plain terms
- Carry
- What spills over when a column adds up to 10 or more. 7 + 5 = 12, so you write 2 and carry 1 into the next column.
- Dummy node
- A throwaway node placed before the first real result node, so you can append without a special case for the first digit. At the end you return dummy.next.
- Tail pointer
- A pointer that always sits on the last node built so far, so each new digit can be attached in one move instead of walking the whole list again.
Each cell is one digit of the result being built, ones digit first
out1—
out2—
out3—
Statusinit
Nothing is built yet, and the carry starts at 0.
What happens in this step
digitsA = [2, 4, 3] (the number 342) digitsB = [5, 6, 4] (the number 465) carry = 0 result = empty Both pointers stand on the ones digit, the head of each list.
Step 1 of 6
Steps to visualize
- The row is the answer under construction; a dash means that digit has not been produced yet.
- Each round adds one digit from each input plus the carry.
- The last digit of that sum is written into the next empty cell.
- Anything above 9 becomes the carry for the following round.
- The loop keeps going while either list still has digits or the carry is not zero.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
out1—
out2—
out3—
Statusinit
Nothing is built yet, and the carry starts at 0.
What happens in this step
digitsA = [2, 4, 3] (the number 342) digitsB = [5, 6, 4] (the number 465) carry = 0 result = empty Both pointers stand on the ones digit, the head of each list.
Step 1 of 6
Solution
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function toList(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
head = new ListNode(values[i], head);
}
return head;
}
function toArray(head) {
const out = [];
for (let node = head; node !== null; node = node.next) {
out.push(node.val);
}
return out;
}
function addTwoNumbers(digitsA, digitsB) {
let a = toList(digitsA);
let b = toList(digitsB);
const dummy = new ListNode(0);
let tail = dummy;
let carry = 0;
while (a !== null || b !== null || carry !== 0) {
const sum = (a === null ? 0 : a.val) + (b === null ? 0 : b.val) + carry;
carry = Math.floor(sum / 10);
tail.next = new ListNode(sum % 10);
tail = tail.next;
a = a === null ? null : a.next;
b = b === null ? null : b.next;
}
return toArray(dummy.next);
}- Time
- O(n)
- Space
- O(n)
Test cases
| Input | Expected | Covers |
|---|---|---|
digitsA = [2, 4, 3], digitsB = [5, 6, 4] | [7, 0, 8] | example from the description |
digitsA = [0], digitsB = [0] | [0] | smallest case, zero plus zero |
digitsA = [9, 9], digitsB = [1] | [0, 0, 1] | the carry creates a digit beyond both inputs |
digitsA = [1, 8], digitsB = [0] | [1, 8] | one list runs out long before the other |
digitsA = [5], digitsB = [5] | [0, 1] | two single digits that add up to ten |
digitsA = [9, 9, 9, 9, 9, 9, 9], digitsB = [9, 9, 9] | [8, 9, 9, 0, 0, 0, 0, 1] | a longer sum where the carry ripples through many columns |