Add 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 contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Constraints:
- The number of nodes in each linked list is in the range
[1, 100]. 0 <= Node.val <= 9- It is guaranteed that the list represents a number that does not have leading zeros.
There are a couple of ways to solve this problem both involving traversing the linked lists and doing arithmetic on the values. One way is to traverse the lists and build the actual numerical value of each input and do normal addition on the results. You would then need to create a new list based on the sum. The other way is to look at it as if you were back in grade school doing arithmetic problems and just sum each node (column) and pass any carryover to the next node. Lets take a look at how we would do that.
Lets start with the problem skeleton:
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
}
Let's set up some variables that we will need to keep track of where we are in our traversal of the inputs. We will need to keep separate variables as we aren't guaranteed that the input lists will have the same length. This means we could run out of nodes in one list before we finish traversing the other list.
//...
var addTwoNumbers = function(l1, l2) {
let node1 = l1
let node2 = l2
}
We also need a way to keep track of the carryover from one node to the next. Lets add that next.
//...
var addTwoNumbers = function(l1, l2) {
let node1 = l1
let node2 = l2
let carryover = 0
}
And finally we will need some way to track our new list that we will be creating as we traverse and do our math. Lets create a new ListNode and set a pointer to the head of the node. We will start it with a dummy value of 0 since it will be easier to just ignore this when it's time to return our list than it would be to set up special checks in the looping process to make sure our pointer actually points to something. We need to also track where in our new list we are similar to what we did with the input lists. Let's create a variable for that as well.
//...
var addTwoNumbers = function(l1, l2) {
let node1 = l1
let node2 = l2
let carryover = 0
let newListPointer = new ListNode(0)
let currentNode = newListPointer
}
Now that we have the setup out of the way, we need to figure out how to traverse the lists, adding up the values (if they exist) and keeping track of any carryover. We need to continue to do this while either of the lists still have values or there is still a carryover that needs to be applied. Let's set up that loop.
while (node1 !== null || node2 !== null || carryover !== 0) {
}
Next we need to find the values that we need to add up for the current node of our new list. Even though we make a check for null in the while loop we still need to make that check when getting the value as one or both of the nodes could still be null. We also need to add any carryover we have kept track of from the previous calculations.
while (node1 !== null || node2 !== null || carryover !== 0) {
let val1 = node1 !== null ? node1.val : 0
let val2 = node2 !== null ? node2.val : 0
let sum = val1 + val2 + carryover
}
We now have the sum from the current node values, we just need to take that and turn it into an integer and a carryover. We will use the modulo operator to get the integer part and then divide the value by ten to get the "tens" column potion. JavaScript number division works as floating point division so we also need to make sure we only keep the integer portion. We will use the Math.floor() built in to do that.
while (node1 !== null || node2 !== null || carryover !== 0) {
let val1 = node1 !== null ? node1.val : 0
let val2 = node2 !== null ? node2.val : 0
let sum = val1 + val2 + carryover
let newValue = sum % 10
carryover = Math.floor(sum / 10)
}
ll that's left to do in the loop is to assign all these values to the correct variables that we are tracking. We already did that with the carryover value. We just need to do that with the new list values. We will create a new node with the new value we just calculated and assign that back to the next value of the currentNode which is the tail of the new list that we are building up. Once we set that we can set then currentNode (or tail of the list) to be the new node we just created.
while (node1 !== null || node2 !== null || carryover !== 0) {
let val1 = node1 !== null ? node1.val : 0
let val2 = node2 !== null ? node2.val : 0
let sum = val1 + val2 + carryover
let newValue = sum % 10
carryover = Math.floor(sum / 10)
let newNode = new ListNode(newValue)
currentNode.next = newNode
currentNode = newNode
}
Almost there! We still need to make sure that we are advancing through the input lists before we start the loop over again. The tricky part here is that if either of the nodes are already null they won't have a next to advance to. One more check for that and if the node exists we go ahead and move it to the next, if not we leave it as null.
while (node1 !== null || node2 !== null || carryover !== 0) {
let val1 = node1 !== null ? node1.val : 0
let val2 = node2 !== null ? node2.val : 0
let sum = val1 + val2 + carryover
let newValue = sum % 10
carryover = Math.floor(sum / 10)
let newNode = new ListNode(newValue)
currentNode.next = newNode
currentNode = newNode
node1 = node1 !== null ? node1.next : null
node2 = node2 !== null ? node2.next : null
}
There you go! We now have our new list of summed nodes built up. If you are wondering about the carryover, just remember we keep looping even if both node have been traversed completely if we have some carryover that isn't 0. All we have left to do is return the new list that we built up. But remember in the beginning we added in the node with a value of 0? I told you that would help us to not have a bunch of checks for null? Well it's still the head of our new list so if we return the list now it would be one place off. The easy part of these lists is you can just return the newListPointer.next. That returns everything that we built up but leaves off the 0.