Every now and then I share a technical problem I worked on for the week and explain it in the hopes of growing from the experience and sharing what I've learned. This time the problem is the "Add Two Numbers" problem.
Before Solving I'd Recommend Being Familiar With
Objects
Constructors
Linked Lists
Before going to the solution read the problem set up and give it a try here if you haven't already.
Concepts Before Code
If you read the description on LeetCode you know your function receives two linked lists as arguments and each list's nodes represent the digits that make up a single, non-negative number:
In the example that means the linked list of 2->4->3 really represents the number 342 because the problem says they're stored in reverse order. So when your function gets the list 2->4->3 and list 5->6->4 it's supposed to add the two actual numbers together and put the digits of that sum in a linked list that's also in reverse order. Unsurprisingly, you're really adding two numbers just like the problem says.
A Clue Before a Solution
Think of how you would add two numbers together with a pencil and paper, could you adapt that algorithm to adding the numbers represented by the linked lists?
Solution
The approach for this solution is to add the two numbers like you would using a pencil and paper. We know the linked lists are reversed so the number 465 would be stored as 5->6->4 where the digits have the following place values:
5 is in the one's place
6 is in the ten's place
4 is in the hundred's place
When you think of how you add on paper you'd start by adding the digits in the one's place and carry any leftover to the ten's, add the digits in the ten's place and carry any leftover to the hundreds, etc.
Thinking about the problem this way can help because:
The digits are already stored in reverse order, one's place first, so you could add them the same way as you would on paper.
The pencil paper method works like a loop and stops when both numbers are out of digits or carry values to add together.
With all that in mind here's the code:
The solution starts out with creating a new ListNode instance whose val attribute will be set to 0 and next will be set to null.
/**
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 list = new ListNode();
// initially currentNode is head let currentNode = list; let sum = 0; let carry = 0;
while (l1 || l2 || sum > 0) {
if (l1) { sum = sum + l1.val; l1 = l1.next; }
if (l2) { sum = sum + l2.val; l2 = l2.next; }
if (sum > 9) { carry = 1; sum = sum - 10; }
currentNode.next = new ListNode(sum); currentNode = currentNode.next;
sum = carry; carry = 0; }
return list.next; }
CurrentNode is set to the reference of the list object because that will act as the head of the linked list at first but be updated in the loop that follows.
The loop runs while at least one of the linked lists still contains digits (or while the node isn't null) or if sum is greater than zero because it means that there is a carry value to add.
The first two if conditions: They add their node's values to the sum and set the node to the next digit to be added.
The last if condition: If the sum is greater than 9 it means that a carry value is required and the loop starts with the carry the next run.
At the end of each loop this code currentNode.next = new ListNode(sum); currentNode = currentNode.next; sets the next node in the list to be the sum just found from that iteration. The first run that would be the one's place, next the tens place, and so on. Finally, you can return the list's next value, which is a list of digits stored in reversed order representing the final sum.
Because the list's next node is returned the returned list doesn't start with a val attribute of zero which is the predefined val when list was first created.
Where I initially went wrong
This one tripped me up for a while because I was following the example too closely and treating it as steps in an algorithm to follow. My original process was to reverse each provided linked lists, do some operation to add those node values together based on their place value, and insert the digits of the sum into a new linked list in reverse again.
This ended up producing some huge numbers for some of the larger test cases which made me rethink my approach.
I hope this helps others who may have worked on this problem!