The Linked List: ADD TWO NUMBERS
Tags: linkedlist, beginners, leetcode, javascript
Published: 2022-04-14 18:24:59

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](https://leetcode.com/problems/add-two-numbers/).

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/aata9vh8z7ck88psednv.jpeg)

---

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9x9qi2zq05dyayms3sfc.png)

---

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.

```javascript
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.

```javascript
...
  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.

```javascript
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.

```javascript
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:

```javascript
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.

```javascript
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.

```javascript
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_.

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

Let's put all together:

```javascript
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 Complexit**y 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!