Add Two Numbers LeetCode Solution

Last updated on October 10th, 2024 at 12:45 am

Here, We see Add Two Numbers LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

List of all LeetCode Solution

Topics

Linked List, Math

Companies

Adobe, Airbnb, Amazon, Bloomberg, Microsoft

Level of Question

Medium

Add Two Numbers LeetCode Solution

Add Two Numbers LeetCode Solution

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]

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.

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.

1. Add Two Numbers Leetcode Solution 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;
    }
};

1.1 Explanation

  1. Initialize sum to 0, l3 (the resulting list) to NULL, and node as a pointer to l3.
  2. Loop until l1, l2, and sum are all null or zero.
  3. Add the values of l1 and l2 to sum if they are not NULL, and move to the next nodes.
  4. Create a new node with the value sum % 10 and set it as the next node.
  5. Update sum to sum / 10 to handle carry-over.
  6. Update node to the next pointer.
  7. Return l3.

1.2 Time Complexity

Θ(m + n), where n and m are the lengths of the input lists.

1.3 Space Complexity

Θ(m + n), for the new list.

2. Add Two Numbers Leetcode Solution 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;
}

2.1 Explanation

  1. Create a dummy head node for the result list.
  2. Initialize p and q to point to the heads of l1 and l2, and curr to dummyHead.
  3. Initialize carry to 0.
  4. Loop until both p and q are null.
  5. Sum the values of p and q with carry.
  6. Update carry to sum / 10 and create a new node with sum % 10.
  7. Move curr to the next node and p and q to their next nodes.
  8. If there’s a remaining carry, add a new node.
  9. Return dummyHead.next.

2.2 Time Complexity

Θ(m + n), where n and m are the lengths of the input lists.

2.4 Space Complexity

Θ(m + n), where n and m are the lengths of the input lists.

3. Add Two Numbers Leetcode Solution 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
};

3.1 Explanation

  1. Initialize node to null.
  2. Get the carry value from the third argument.
  3. If either l1 or l2 is not null:
    • Get values of l1 and l2, set to 0 if null.
    • Calculate val as the sum of val1, val2, and carry.
    • Create a new node with val % 10.
    • Recursively call addTwoNumbers with next nodes and val >= 10.
  4. If both l1 and l2 are null but carry is true, create a node with value 1.
  5. Return node.

3.2 Time Complexity

Θ(m + n)

3.3 Space Complexity

Θ(m + n), due to recursion stack.

4. Add Two Numbers Leetcode Solution 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

4.1 Explanation

  1. Initialize result with a dummy node and result_tail to result.
  2. Initialize carry to 0.
  3. Loop until l1, l2, or carry are not null/zero.
  4. Get val1 and val2, defaulting to 0 if l1 or l2 are null.
  5. Calculate carry and out using divmod.
  6. Create a new node with out and move result_tail.
  7. Move l1 and l2 to their next nodes.
  8. Return result.next.

4.2 Time Complexity

Θ(m + n)

4.3 Space Complexity

Θ(m + n)

Scroll to Top