In this LeetCode challenge we’re asked to add together two numbers. Seem simple? Well it isn’t. Of course, it’s a lot simpler than the way it’s explained on the page, but I suppose that’s a matter of opinion… however I encourage you to read the official one first.
Head hurting? Good stuff. Here’s my translation: Given two linked lists, which each represent a number in reverse order, add them together, and return the answer in the same format (a reverse-ordered linked list).
Solution #1: Converting the lists to numbers
My very first instinct on this question was to convert the linked lists to their numerical counterparts, reverse them, add them together, convert the answer to a reverse-ordered linked list, and then return it. So here is what I came up with:
First we establish a function to convert a reverse-ordered linked list into an array of digits, which we call ConvertReverseListNodeToArray. What this function does, is that it takes a linked list, and recursively works its way through the list until it reaches the end, adding each value to an array as it goes. In addition, because we add each layer after the next layer in the list, we end up (intentionally) reversing the original order.
Next up, we convert both lists using the above function, .join() them into numbers, and add them together to get the numerical answer… which we must now convert back into a reverse-ordered linked list.
First up on the back-stretch, we convert the total number to an array for easier traversal. Next we loop through the array, creating a ListNode for each number and adding it to an overall linked list. Once again, because of the order in which we’re doing this, the new list ends up being an (intentionally) reversed version of the original array.
So there you have it, a somewhat straightforward and more mathematical approach to the problem.
Solution #2: While loop
This approach is based on a solution posted by LeetCode user cosde. It works by running a while loop, which continues until all list elements have been traversed. On each iteration, it adds the two values together, checks if there’s a carry value (if the total exceeds 10), and if so passes it to the next iteration. Very elegant, and highly readable:
Solution #3: Recursive function
Another approach that I really liked was to use a recursive function with an optional parameter. This approach was originally posted by anhduc130, with my only alterations being to improve readability. It’s similar to the while loop approach above, but… without the while loop!
The way this approach works is that it makes use of JavaScript’s arguments object, which contains all the arguments passed into a function, even if they weren’t specified in the function header. The reason this is important is that LeetCode already specify the function header, and this can’t be changed, but by using the arguments variable we’re able to get around this. Now, as has been posted in the comments to the above solution, there are potential edge-case issues with this approach, however it does pass on LeetCode, and looks really great:
For each call of the function, it first adds the two ListNode’s values together (if they exist), as well as any value carried over from a previous run (again if it exists), and then calls the function again on the next level of the ListNodes (if they exist), optionally passing a carry value to also be added in (if that exists!).
Top comments (0)