Hey There!

Another day where I work towards becoming a better version of my developer self. Today's LeetCode Challenge was titled Add Two Numbers, you can find the problem here. It is rated a medium challenge and is a linked list problem.

As with most of my other questions, I logged into LeetCode today and I decided to challenge myself with a medium problem. That was where I made my mistake.

Add Two Numbers

I logged into my account today and decided to try my hand at a medium challenge. I selected the first LeetCode problem. The problem provides us with two singly linked lists. In LeetCode's representation of the problem, the lists were presented in square brackets. I saw this and immediately assumed they were arrays and solved the problem that way.

The problem would send give us two lists representing numbers in reverse and the problem required us to add the two numbers and return the sum, also in reverse (in a list).

The Approach

I decided to lay out my parameters and returns and set up the examples. I pulled the question from LeetCode and pasted it into my VS Code and started typing away.

Parameters:

We are passed two linked lists. The lists will represent a number. The number will be reversed. The lists passed will not have any special characters for us to worry about, letters or indexes. The lists will not start with 0 either.

Returns:

Return the sum of the two linked lists. Reverse the order, sum the two lists, get the result and then return the result as a reversed list. Similar to the parameters passed.

Examples:

Similarly to other problems I've done in the past, I just yoinked examples from LeetCode and used them as my test cases.

Lessons Learned

The first time around I solved this problem, I managed to get through it fairly easily. I decided that since I was being passed arrays, I would simply reverse the arrays, turn the strings into numbers, add them and then do the reverse for the result.

I got caught on my result. When I was returning the result, I was returning an array of strings representing numbers instead of an array of numbers, as displayed below.

// My answer
[ '8', '9', '9', '9', '0', '0', '0', '1'] 

// Solution I was targeting
[ 8, 9, 9, 9, 0, 0, 0, 1]

I tried to use a forEach loop on the solution to convert each element into an array, but it wasn't working. I tried manipulating my code a few times to no avail. I instead decided to use the map method and just return the answer in a new array instead of manipulating the result array I had.

I took my approach and pasted it into LeetCode and I kept coming back with an error. You cannot run the reverse method on the first array (list). Again, I was perplexed. I copied my code into the console and ran it and the solution worked there. I kept sifting through my code looking for the bug that kept breaking the array method that was supposed to run on an array but couldn't find it. After consulting with developer friends, again, I learned that LeetCode, while displaying linked lists as arrays, aren't actually arrays and must be treated as objects.

Well, I had not done any linked list questions before but I was determined to finish this question since I technically already solved it, but in the wrong way.

After a little bit of thinking, and not coming up with a solution, I decided to just look at the solutions instead and study that.

I started looking for a solution in JavaScript and things were not making sense. The solution I found was using this.val and this.next. If you're as confused as I was, LeetCode actually generates a function for linked lists for you at the start of their code editor.

// Definition for singly-linked list.
function ListNode(val, next) {
     this.val = (val===undefined ? 0 : val)
     this.next = (next===undefined ? null : next)
}

Linked List explanation

So, how did the person approach solving the problem? Well, from my understanding, you have to start off with a few things. You should create a variable to hold the sum of your lists, you have to know what node you are on, and you must point at the head of your results list.

As you approach the lists, you must add the value of each node to the sum variable you created. Once you've found the sum of the first node, you assign it to the first node in your result list. You will then tell your program to step into the next node and repeat the process. This was done via a while loop checking to make sure that both list 1 and list 2 still had values left in them.

But what happens if the sum of the two lists is greater than 10?

Well, if the sum of your nodes is double-digit, we can't insert the answer it into a single result node. It would break our result and that's not how math typically works. To overcome this, if our result was double-digit, we would start by counting the sum of our next nodes at 1 instead of 0. This was taken care of via a conditional.

Throughout the whole process, our result variable does not iterate through as the while loop is running. The variable will sit outside of the loop. However, because our result variable only points at the head of the result list and does not actually represent the node of the head of the results list, we must tell it to step into the results list after we've found our solution. The thing with singly linked lists is when you return the head of the list, because of the way it's structured and the fact that each node points to the next node, you only need to return the first node and each node will follow.

As always, I've provided the solutions I put together at the end of this article if you would like to make more sense of what I wrote out here. I also wrote comments on the code in an attempt to make sense of what was happening.

Solution

Wrong, array solution:

var addTwoNumbers = function(l1, l2) {
    // reverse the two lists, join them and make them into numbers. 
    let list1 
    let list2

    // if both arrays are 1 element long no need to reverse
    if (l1.length === 1 && l2.length === 1 ){
        list1 = l1
        list2 = l2
    } else if (l1.length > 1 && l2.length === 1) {
        list1 = l1.reverse().join('')
        list2 = l2
    } else if (l1.length === 1 && l2.length > 1) {
        list1 = l1
        list2 = l2.reverse().join('')
    } else {
        list1 = l1.reverse().join('')
        list2 = l2.reverse().join('')
    }

    // add the two lists
    let result =  +list1 + +list2
    let resNum = String(result).split('').reverse()
    let ans = resNum.map(x=> +x)

    // split the answer and return in reverse as an array
    return ans
};

Linked list solution:

/**
 * 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) {

    // Initialize your sum
    let sum = 0;
    // Initialize the head of the result list 
    let current = new ListNode(0);
    // Set the result list as your head node.
    let result = current;


    // Run through the lists and add them to your sum. 
    while(l1 || l2) {

        if(l1) {
            sum += l1.val;
            l1 = l1.next;
        }

        if(l2) {
            sum += l2.val;
            l2 = l2.next;
        }

        // Place the remainder of the sum into your next result list node. 
        // This is because we are dealing with each value individually. 
        current.next = new ListNode(sum % 10);
        current = current.next;

        // if the sum is greater than 9 we to carry forward the 1. 
        // So instead of starting our next iteration at sum = 0,
        // we start at sum = 1.
        sum = sum > 9 ? 1 : 0;
    }

    // If there still remains a remainder because our final digits 
    // were grater than 9, put the extra 1 into a final node.
    if(sum) {
        current.next = new ListNode(sum);
    }

    // Result is still pointing outside of the result linked list, 
    // so we must step into the head of the list and return. 
    // Returning the head of a singly linked list will return the full list.
    return result.next;
};

Thank you for reading. I hope you learned something.