DEV Community

Duncan McArdle
Duncan McArdle

Posted on

1

LeetCode problem #2 — Add two numbers (JavaScript)

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:

var addTwoNumbers = function (l1, l2) {
// Convert a ListNode to an array of its digits in reverse order
function ConvertReverseListNodeToArray(listNode) {
// Initialise an array to return
let returnedArray = [];
// Check if there is another level to the ListNode
if (listNode.next != null) {
// Merge the current array with the result of calling the function again on the next level
returnedArray = returnedArray.concat(
ConvertReverseListNodeToArray(listNode.next)
);
}
// Add the current node's value to the returned array
returnedArray.push(listNode.val);
// Return the constructed array
return returnedArray;
}
// Convert the ListNodes to Arrays
const l1Array = ConvertReverseListNodeToArray(l1);
const l2Array = ConvertReverseListNodeToArray(l2);
// Add the numbers (after merging them), using BigInt due to LeetCode's edge cases
let newTotal = BigInt(l1Array.join('')) + BigInt(l2Array.join(''));
// Split the total back into an array
splitNewTotal = newTotal.toString().split('');
// Initialise an empty ListNode
let returnedListNode = null;
// Loop through the total value's array
for (let i = 0; i < splitNewTotal.length; i++) {
// Add this digit to the ListNode
returnedListNode = {
val: splitNewTotal[i],
next: returnedListNode,
};
}
// Return the constructed ListNode
return returnedListNode;
};

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:

var addTwoNumbers = function (l1, l2) {
// Initialise a new ListNode to be returned
var newListNode = new ListNode(0);
var headOfNewListNode = newListNode;
// Initialise variables to be utilised on each run
var sum = 0;
var carry = 0;
// While there are elements (or a carried number) to add
while (l1 !== null || l2 !== null || sum > 0) {
// If there's an element in l1 to be added, add it to the sum and move to the next l1 node
if (l1 !== null) {
sum = sum + l1.val;
l1 = l1.next;
}
// If there's an element in l2 to be added, add it to the sum and move to the next l2 node
if (l2 !== null) {
sum = sum + l2.val;
l2 = l2.next;
}
// Check if the sum for these nodes exceeds 10
if (sum >= 10) {
carry = 1;
sum = sum - 10;
}
// Add the sum to the new ListNode, and then move it to the next entry
headOfNewListNode.next = new ListNode(sum);
headOfNewListNode = headOfNewListNode.next;
// Set the sum for the next addition to equal the carry-over (if there was one)
sum = carry;
carry = 0;
}
// Return the constructed ListNode (ignoring the first dummy entry)
return newListNode.next;
};

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:

var addTwoNumbers = function (l1, l2) {
// Initialise the node as null in case no values are added to it (so parent's .next will be null)
let node = null;
// Obtain the secret third argument (or change it to 0)
const carry = arguments[2] ? 1 : 0;
// Check if either an l1 node or l2 node exist to be added together
if (l1 || l2) {
// Obtain the values of the current l1 and l2 nodes (or 0 if they do not exist)
const val1 = l1 ? l1.val : 0;
const val2 = l2 ? l2.val : 0;
// Obtain the .next values of the current l1 and l2 nodes (or null if they do not exist)
const next1 = l1 ? l1.next : null;
const next2 = l2 ? l2.next : null;
// Sum together the two values and the (optional) carry
const sum = val1 + val2 + Number(carry);
// Set the returning node to the sum, with any potential carry removed
node = new ListNode(sum % 10);
// Set the returning node's .next value to be the sum of adding the next two nodes together, along with the current carry (if one exists)
node.next = addTwoNumbers(next1, next2, sum >= 10);
} else if (carry) {
// If a carry was passed in but no values exist to be added, return a node with the carry value in it, and no .next
node = new ListNode(1);
node.next = null;
}
// Return the constucted node
return node;
};

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!).

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more