Hey! Today's algorithm is one of the most popular ones on Leetcode: adding two numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
So, let's say you were given two linked lists: 2 > 4 > 3 and 5 > 6 > 4. To add those numbers, you'd do the reverse of both of them: 342 + 465, which equals 807. Therefore, the output of this problem should be 7 > 0 > 8.
I think one of the trickiest parts of this problem is the issue of the carried number -- if every pair of nodes added to a number less than 10, then there wouldn't be a concern of 'carrying' digits over to the next node. However, as you can see in the example above, adding numbers like 4 and 6 produces a carry, which you have to account for when adding 3 and 4.
In this post, I'll first draw a diagram of how I'm going to approach this problem. Then, in JavaScript, I'll walkthrough my code of the solution.
Approaching The Problem
First, I'll start with two linked lists 1 > 6 > 4 and 2 > 6 > 3. I know the solution I want is another linked list whose value is 3 > 2 > 8. The reason I know that's the solution is that 463 + 362 = 823, and when backwards and put into a linked list, that number is 3 > 2 > 8.
Now, I'll start by getting the value of the first node of both linked lists. 1 + 2 = 3. Since 3 is smaller than 10, no number needs to be carried over, so I'll just put 3 into a new node.
Now I'll move onto the next node in both list. 6 + 6 = 12. Since 12 is not a single digit number, the 1 will be carried over to the next round, and the 2 will be put into a node for the solution.
Next are 4 and 3. 4 + 3 = 7, plus there's the carried over 1 from the previous round. 7 + 1 = 8, and since 8 is a single digit number, we can put it into a new node in the solution.
Since there are no more nodes to check in either linked list, we have our solution: 3 > 2 > 8.
Coding the Solution
The Leetcode problem gives us a function for a singly-linked list, which has the properties of 'value' and 'next' (next points to the next node in the list).
The first thing I'll do in this problem is create a new list, and set a new variable currentNode equal to the list. This list is what will be returned at the end of the problem. Because in the function we'll want to return each node of the list, we can add a return statement at the bottom, using .next.
function addTwoNumbers(l1, l2) {
let list = new ListNode(0);
let currentNode = list;
//...
return list.next;
}
Now, we'll initiate two variables, sum and carry. Sum will hold the value of adding the nodes, and carry will hold any number that'll need to be carried over to the next node. We can start by setting both of these values to 0.
function addTwoNumbers(l1, l2) {
let list = new ListNode(0);
let currentNode = list;
let sum = 0;
let carry = 0;
//...
return list.next;
}
Next, we'll need to create a while loop, which will check the nodes and their values until there are no nodes left to check. If one list is longer than the other, we still will want to add the longer list's nodes to the solution, so we'll have to make sure we continue to check so long as the nodes aren't null. That means the while loop should keep going as long as list 1 isn't null OR list 2 isn't null.
But, there's one more case we have to account for: what if we're done checking both nodes, but there's still a 'carried' value. For example, if the given lists were 5 and 5, then the output should be 0 > 1. Since a number is being carried over, we'll need to enter the while loop again. That means that as long as there's a leftover sum, or sum > 0, or either of the lists still have nodes to be checked, we'll keep going through the while loop.
function addTwoNumbers(l1, l2) {
let list = new ListNode(0);
let currentNode = list;
let sum = 0;
let carry = 0;
while (l1 !== null || l2 !== null || sum > 0) {
//...
}
return list.next;
}
Now we're in the while loop. We'll want to add values to the sum if there are still values to add, so we'll have two very similar if-statements. If a node still has value, then we'll add that value to the sum. We'll then move onto the next node in the list. We'll do the same for both l1 and l2.
function addTwoNumbers(l1, l2) {
let list = new ListNode(0);
let currentNode = list;
let sum = 0;
let carry = 0;
while (l1 !== null || l2 !== null || sum > 0) {
if (l1 !== null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 !== null) {
sum += l2.val;
l2 = l2.next;
}
//...
}
return list.next;
}
Now is the point we have to deal with the possibility of a carried over number. If sum is greater than or equal to 10, then there will be a carry. There's a few ways to check for this, but I like to use division and modulo.
If sum = 13, then we know the carry should be 1. To get the carry, we can divide the sum by 10. Since we don't want a remainder, we can use Math.floor(). Math.floor(13/10) is 1, which is the carry that we want.
For the sum, we just want what's in the ones-digit spot of 13 (aka we just want 3). We'll only be adding 3 to the result. To single out this digit, we can use modulo. 13 % 10 gives us 3, because the remainder of 13/10 is 3.
function addTwoNumbers(l1, l2) {
let list = new ListNode(0);
let currentNode = list;
let sum = 0;
let carry = 0;
while (l1 !== null || l2 !== null || sum > 0) {
if (l1 !== null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 !== null) {
sum += l2.val;
l2 = l2.next;
}
carry = Math.floor(sum / 10);
sum = sum % 10;
//...
}
return list.next;
}
Now, we'll want to add a new node to our solution list, and give it the value of the sum. We'll also want to move over in our list, and reset the currentNode to equal the next node we've just added.
function addTwoNumbers(l1, l2) {
let list = new ListNode(0);
let currentNode = list;
let sum = 0;
let carry = 0;
while (l1 !== null || l2 !== null || sum > 0) {
if (l1 !== null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 !== null) {
sum += l2.val;
l2 = l2.next;
}
carry = Math.floor(sum / 10);
sum = sum % 10;
currentNode.next = new ListNode(sum);
currentNode = currentNode.next;
//...
}
return list.next;
}
Finally, the last thing we'll want to do is move any carry value to sum, setting carry back equal to 0. This way, when the cycle repeats for the next node, the sum will start with any value that was carried over. And, given that our while-loop has a conditional for if sum > 0, if there's a number that's being carried over, then a new node will be made.
function addTwoNumbers(l1, l2) {
let list = new ListNode(0);
let currentNode = list;
let sum = 0;
let carry = 0;
while (l1 !== null || l2 !== null || sum > 0) {
if (l1 !== null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 !== null) {
sum += l2.val;
l2 = l2.next;
}
carry = Math.floor(sum / 10);
sum = sum % 10;
currentNode.next = new ListNode(sum);
currentNode = currentNode.next;
sum = carry;
carry = 0;
}
return list.next;
}
--
Please let me know in the comments if you have any questions or alternate approaches to this problem!
Oldest comments (3)
nice, liked the post.
Code / concept is very clear.
However, it does not make sense why you have
sum > 0in your while loop at first, all the way until you introducesum = carry.You know what,sum=carry is not here because this answer has been copied from LeetCode just 1 variable changed which is currentNode.