Add Two Numbers LeetCode Solution

Last updated on January 12th, 2025 at 03:39 am

Here, We see Add Two Numbers LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Linked List, Math

Companies

Adobe, Airbnb, Amazon, Bloomberg, Microsoft

Level of Question

Medium

Add Two Numbers LeetCode Solution

1. Problem Statement

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.

Add Two Numbers LeetCode Solution example
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]

2.1 Algorithm

Add Two Numbers LeetCode Solution algorithm
Fig – Visualization of the addition of two numbers: 342 + 465 = 807
Each node contains a single digit and the digits are stored in reverse order.

2.2 Pseudocode

  • Initialize the current node to the dummy head of the returning list.
  • Initialize carry to 0.
  • Initialize p and q to the head of l1 and l2 respectively.
  • Loop through lists l1 and l2 until you reach both ends.
    • Set x to the node p‘s value. If pp has reached the end of l1, set to 0.
    • Set y to node q‘s value. If q has reached the end of l2, set to 0.
    • Set sum = x+y+carry.
    • Update carry=sum/10.
    • Create a new node with the digit value of (sum mod 10) and set it to the current node’s next, then advance the current node to the next.
    • Advance both p and q.
  • Check if carry=1, if so append a new node with digit 1 to the returning list.
  • Return the dummy head’s next node.

3. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Linked List Traversal”. This pattern involves iterating through one or more linked lists, performing operations on their nodes, and constructing a new linked list as a result. 

4. How the Code Works

  1. The goal of the code is to add two numbers represented as linked lists, where each node contains a single digit. The digits are stored in reverse order, meaning the least significant digit comes first.
  2. The code iterates through both linked lists (l1 and l2) simultaneously, adding corresponding digits along with any carry from the previous addition.
  3. If one list is shorter, the missing digits are treated as 0.
  4. A new linked list is constructed to store the result, with each node containing the sum of the corresponding digits modulo 10. The carry (if any) is propagated to the next iteration.
  5. If there is a carry left after processing all nodes, it is added as a new node at the end of the result list.

5. Code Implementation in Different Languages

5.1 Add Two Numbers C++

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int sum=0;
        ListNode *l3=NULL;
        ListNode **node=&l3;
        while(l1!=NULL||l2!=NULL||sum>0)
        {
            if(l1!=NULL)
            {
                sum+=l1->val;
                l1=l1->next;
            }
            if(l2!=NULL)
            {
                sum+=l2->val;
                l2=l2->next;
            }
            (*node)=new ListNode(sum%10);
            sum/=10;
            node=&((*node)->next);
        }        
        return l3;
    }
};

5.2 Add Two Numbers Java

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

5.3 Add Two Numbers JavaScript

var addTwoNumbers = function(l1, l2) {
    let node = null
    const carry = arguments[2]
    if (l1 || l2) {
        const val1 = l1 ? l1.val : 0
        const val2 = l2 ? l2.val : 0
        const next1 = l1 ? l1.next : null
        const next2 = l2 ? l2.next : null
        const val = carry ? val1 + val2 + 1 : val1 + val2
        node = new ListNode(val % 10)
        node.next = addTwoNumbers(next1, next2, val >= 10)  
    } else if (carry) {
        node = new ListNode(1)
        node.next = null
    }
    return node
};

5.4 Add Two Numbers Python

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        result = ListNode(0)
        result_tail = result
        carry = 0
                
        while l1 or l2 or carry:            
            val1  = (l1.val if l1 else 0)
            val2  = (l2.val if l2 else 0)
            carry, out = divmod(val1+val2 + carry, 10)    
                      
            result_tail.next = ListNode(out)
            result_tail = result_tail.next                      
            
            l1 = (l1.next if l1 else None)
            l2 = (l2.next if l2 else None)
               
        return result.next

6. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(n)O(n)
JavaO(n)O(n)
JavaScriptO(n)O(n)
PythonO(n)O(n)
  • The code in all languages follows the Linked List Traversal pattern and efficiently solves the problem of adding two numbers represented as linked lists.
  • The iterative implementations (Java, Python, C++) are more space-efficient compared to the recursive JavaScript implementation.
Scroll to Top