Add two numbers linked list javascript

LeetCode problem #2 Add two numbers (JavaScript)

Duncan McArdle

Nội dung chính Show

• LeetCode problem #2 Add two numbers (JavaScript)
• Solution #1: Converting the lists to numbers
• Solution #2: While loop
• Solution #3: Recursive function

Oct 29, 2020·3 min read

In this LeetCode challenge were asked to add together two numbers. Seem simple? Well it isnt. Of course, its a lot simpler than the way its explained on the page, but I suppose thats a matter of opinion however I encourage you to read the official one first.

Head hurting? Good stuff. Heres 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 were 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 theres 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. Its similar to the while loop approach above, but without the while loop!

The way this approach works is that it makes use of JavaScripts arguments object, which contains all the arguments passed into a function, even if they werent specified in the function header. The reason this is important is that LeetCode already specify the function header, and this cant be changed, but by using the arguments variable were 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 ListNodes 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!).