The Linked List: ADD TWO NUMBERS

By this post, I’d like to start a series of Leetcode problems on Linked Lists, one of the common interview questions. Today, we’ll be walking through the Add Two Numbers Problem.

The problem is, given two non-empty linked lists representing two integers where digits are stored in reverse order, add their digits and return the sum as a linked list.

To solve this problem, we are going to use the column method from elementary Math: going through the lists from the head, digits-by-digits sum numbers until we reach the end of both lists: list1 AND list2 (because they may have different lengths).

The first thing we are going to do here is to create a new list since we have to return it at the end.

Using the provided function definition, we create the very first node, with a value equal to 0 by default. That will be the head of our list called list (we always need to remember the very first node to return the whole chain). Actually, we will return the list starting from the next node to skip this first 0.

We also need the second cursor currentNode for pointing to the current node we are working on within the current iteration. Initially, it’s equal to the list’s head but then we will use it to iterate over the list manually.

const addTwoNumbers = (list1, list2) => {
  let list = new ListNode(0); //create a new list
  let currentNode = list; //cursor initialized to list's head
...

  return list.next; //return head's next node (to skip the first 0)
};

Then we need to initialize two additional variables: sum which will hold the sum of two digits, and carry which will hold the digit “carried over” the next iteration in case the sum of two digits will be >= 10.

...
  let sum = 0;
  let carry = 0;
...

};

Next, we are going to iterate over two lists and sum up their values. We will use the while loop here to run the code unless we reach the end of either of the lists. We also need to think about the case if we still have the carry reminder left by the end of the cycle, so this will be the third condition to check.

while (list1 || list2 || sum > 0) { //while list !== null or there's still reminder
...
}

Within the loop, we will have two if statements in case the lists have different lengths. The pseudocode for the iteration for each list is following:

1. Check if the current list node still exists (not equal to null).
2. Add its value to the sum.
3. Move the pointer cursor to the next node.

while (list1 || list2 || sum > 0) { //while list !== null or there's still reminder
    if (list1) { //check if list !== null in case lists have different sizes
      sum += list1.val;
      list1 = list1.next; //move the pointer
    }
    if (list2) {
      sum += list2.val;
      list2 = list2.next;
    }
...
}

By the end of one iteration, we have the sum value.

Now it’s time to check if it is >= 10. If it is (for example, the sum is 12), we will take only the second digit 2, and the first one 1 will be carried over the next iteration.

To split this number into two digits, we’ll use Math division and modulo operation:

while (list1 || list2 || sum > 0) {
...
    carry = Math.floor(sum / 10);
    sum = sum % 10;
...
}

Now we can add a new node to the output list and give it the value of the sum.

Again, by pushing a new node to the end of the list, we are: (1) allocating memory for it, (2) linking it with the current node, (3) initializing its value, and (4) setting up its pointer to null by default.

while (list1 || list2 || sum > 0) {
...
//add a new node to the list, link it with the current node, and give it the value of the sum
    currentNode.next = new ListNode(sum);
...
}

And one more thing we need to do here is to advance the currentNode cursor to the new node we just added for the next iteration.

while (list1 || list2 || sum > 0) {
...
   //add a new node to the list, link it with the current node, and give it the value of the sum
    currentNode.next = new ListNode(sum);

  //move the cursor to the new node
    currentNode = currentNode.next;
...
}

Lastly, we need to initialize the sum to the carrier before the next iteration (since we’ll add the carrier to the sum in the next round) and reset the sum.

while (list1 || list2 || sum > 0) {
...
    sum = carry;
    carry = 0;
}

Let's put all together:

const addTwoNumbers = (list1, list2) => {
  let list = new ListNode(0); //create a new list
  let currentNode = list; //cursor initialized to list's head

  let sum = 0;
  let carry = 0;

  while (list1 || list2 || sum > 0) { //while list !== null or there's still reminder
    if (list1) { //check if list !== null in case lists have different sizes
      sum += list1.val;
      list1 = list1.next; //move the pointer
    }
    if (list2) {
      sum += list2.val;
      list2 = list2.next;
    }

    carry = Math.floor(sum / 10);
    sum = sum % 10;

    //add a new node to the list, link it with the current node, and give it the value of the sum
    currentNode.next = new ListNode(sum);

    //move the cursor to the new node
    currentNode = currentNode.next;

    sum = carry;
    carry = 0;
  }

  return list.next; //return head's next node (to skip the first 0)
};

We're done!

What about complexity?

Time Complexity of this approach is O(n) where n is the maximum number of nodes of the longest list since we have to traverse the lists.
Space Complexity: O(n) where n is the maximum number of nodes of the longest list since we create a new list in the memory.

Next time, we’ll discuss two more advanced problems:
ADD TWO NUMBERS II
ADD TWO NUMBERS WITH METHODS

I hope this helped! Please let me know if you have additional comments or questions!