2. Add Two Numbers

 

Add Two Numbers

Problem Description

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.

 

Example 1:

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

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

 

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

Let's code it!

var addTwoNumbers = function(l1, l2) {
    let values = [];
    let overflow = 0;
    while (l1.next || l2.next) {
        const value = (l1.val + l2.val + overflow) % 10;
        overflow = l1.val + l2.val + overflow >= 10 ? 1 : 0;
        values.push(value);

        l1 = l1.next || new ListNode(0);
        l2 = l2.next || new ListNode(0);
    }
    const value = (l1.val + l2.val + overflow) % 10;
    overflow = l1.val + l2.val + overflow >= 10 ? 1 : 0;
    values.push(value);
    if (overflow === 1) {
        values.push(1);
    }
    let node = undefined;
    values.reverse().forEach(item => {
        if (node === undefined) {
            node = new ListNode(item);
        } else {
            const newNode = new ListNode(item);
            newNode.next = node;
            node = newNode;
        }
    });
    return node;
};

Runtime: 124 ms, faster than 36.10% of JavaScript online submissions for Add Two Numbers.
Memory Usage: 38.9 MB, less than 18.05% of JavaScript online submissions for Add Two Numbers.

Complexity analysis

Time Complexity

We are traversing through the complete list L1 or L2 which needs O(N).

Space Complexity

We are using 1 extra space of size N to store values, hence space complexity is O(N).

Resources:

https://github.com/PraveenMistry/leetCode

https://medium.com/@praveenmistry/linked-list-javascript-part-3-1-d504f0c9b54e

https://medium.com/@praveenmistry/doubly-linked-list-javascript-part-3-2-1209068fb788

Conclusion

That’s all folks! In this post, we solved LeetCode problem #2. Add Two Numbers

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!