Last updated on July 13th, 2024 at 04:04 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
Table of Contents
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.
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
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
- Initialize sum to 0, l3 (the resulting list) to NULL, and node as a pointer to l3.
- Loop until l1, l2, and sum are all null or zero.
- Add the values of l1 and l2 to sum if they are not NULL, and move to the next nodes.
- Create a new node with the value sum % 10 and set it as the next node.
- Update sum to sum / 10 to handle carry-over.
- Update node to the next pointer.
- 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
- Create a dummy head node for the result list.
- Initialize p and q to point to the heads of l1 and l2, and curr to dummyHead.
- Initialize carry to 0.
- Loop until both p and q are null.
- Sum the values of p and q with carry.
- Update carry to sum / 10 and create a new node with sum % 10.
- Move curr to the next node and p and q to their next nodes.
- If there’s a remaining carry, add a new node.
- 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
- Initialize node to null.
- Get the carry value from the third argument.
- 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.
- If both l1 and l2 are null but carry is true, create a node with value 1.
- 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
- Initialize result with a dummy node and result_tail to result.
- Initialize carry to 0.
- Loop until l1, l2, or carry are not null/zero.
- Get val1 and val2, defaulting to 0 if l1 or l2 are null.
- Calculate carry and out using divmod.
- Create a new node with out and move result_tail.
- Move l1 and l2 to their next nodes.
- Return result.next.
4.2 Time Complexity
Θ(m + n)
4.3 Space Complexity
Θ(m + n)