2. Add Two Numbers 🚀

Solution Developed In:

The Question

For this article we will be covering Leetcode's '2. Add Two Numbers' question. A medium question that is a little tricky.
Question:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Explaining The Question

This Question is rated Medium. Which would be fair to say if you've just started learning Linked Lists. See this question is a really odd one. It's more of a maths question with Linked Lists thrown in.

We're given 2 linked lists. Which represents two numbers (2->4->3, 5->6->4). We need to add the numbers together and return the result as a list. Which sounds really tough to do.

The way we're going to solve this is by going back to when you first learnt how to add big numbers with that carry system. We're going to implement that exact system.

We're going to go through our lists at the exact same time, with a pointer on each list. That'll be our column. We will add up all those numbers in that column (2 + 5 = 7). If that number is greater than 9, we know we need to carry that number to the next column. So what we do is we {sum} - 10. With a note to carry a 1 to the next col. We then take that now < 10 sum and create it's own ListNode. Moving to all the next list nodes.

We repeat this until we have no more lists left and more carry numbers left.
It's the exact same system that many people are taught at a young age.

---

Big O Notation:

• Time Complexity: O(n + m) | Where n / m is the length of the list we're traversing.
• Space Complexity: O(1) | We don't use extra space and we don't count the output as extra space as it's expected.

Leetcode Results:

See Submission Link:

---

The Solution

var addTwoNumbers = function (l1, l2) {

    const sentinel_node = new ListNode(0);
    let   number_carry  = 0;
    let   head          = sentinel_node;
    let   sum           = 0;

    while (l1 || l2 || sum) {

        // Add the numbers together.
        sum += (l1) ? l1.val : 0;
        sum += (l2) ? l2.val : 0;

        // Do we need a number carry?
        if (sum >= 10) {
            number_carry = 1;         // Add carry
            sum          = sum - 10;  // Update sum to 1 int
        }

        // Add new node (With our new sum)
        head.next = new ListNode(sum, null);
        head      = head.next;

        // Move both lists forward if possible
        l1 = (l1) ? l1.next : null;
        l2 = (l2) ? l2.next : null;


        // Carry the 1 if so.
        sum          = number_carry;
        number_carry = 0;
    }

    return sentinel_node.next;
};