# Add Two Numbers II Leetcode Solution

Difficulty Level Medium

System design interview questions can be so open-ended, that it's too hard to know the right way to prepare. Now I am able to crack the design rounds of Amazon, Microsoft, and Adobe after buying this book. Daily revise one design question and I promise you can crack the design round.

## Problem Statement

The Add Two Numbers II LeetCode Solution – “Add Two Numbers II” states that two non-empty linked lists represent two non-negative integers where the most significant digit comes first and each node contains exactly one digit. We need to add the two numbers and return the sum as the linked list.

## Example:

`Input:  l1 = [7,2,4,3], l2 = [5,6,4]`
`Output: [7,8,0,7]`

Explanation:

• The most significant digit comes first.
• When we add the above two numbers, we get [7, 8, 0, 7].
`Input:  l1 = [2,4,3], l2 = [5,6,4]`
`Output: [8,0,7]`

Explanation:

• [8, 0, 7] is the sum we get on adding the above two numbers.

## Approach

### Idea:

1. The main idea to solve this problem is to use basis maths to add two linked lists.
2. Reverse both the linked list to add the digits starting from the least significant position.
3. Iterate till both the linked list becomes empty.
4. At any position, extract the digit present at the current position for both the linked lists.
5. If the digit is absent in either of the linked lists, then take the digit as 0 for simplicity.
6. A digit that will be added now to the sum linked list will be the remainder obtained by adding a, b, and carry where:
1. a = digit present at current position for a first linked list.
2. b = digit present at current position for a second linked list.
3. carry = digit that needs to be added.
7. Our new carry would become (a + b + carry) / 10.
8. Continue the above steps for each position, till we get the desired sum linked list.

## Code

### Add Two Numbers II Leetcode C++ Solution:

```class Solution {
public:

ListNode *curr = head, *prev = nullptr;
while(curr != nullptr){
ListNode* next_node = curr->next;
curr->next = prev;
prev = curr;
curr = next_node;
}

return prev;
}

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
l1 = reverse(l1);
l2 = reverse(l2);

int carry = 0;
ListNode* dummy = new ListNode(-1);

ListNode* curr = dummy;

while(l1 != nullptr || l2 != nullptr){
int a = l1 == nullptr ? 0 : l1->val;
int b = l2 == nullptr ? 0 : l2->val;

curr->next = new ListNode((a + b + carry)%10);

carry = (a + b + carry)/10;

curr = curr->next;

if(l1 != nullptr){
l1 = l1->next;
}

if(l2 != nullptr){
l2 = l2->next;
}
}

if(carry > 0){
curr->next = new ListNode(carry);
}

return reverse(dummy->next);
}
};```

### Add Two Numbers II Leetcode Java Solution:

```class Solution {
ListNode curr = head, prev = null;
while(curr != null){
ListNode next_node = curr.next;
curr.next = prev;
prev = curr;
curr = next_node;
}

return prev;
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
l1 = reverse(l1);
l2 = reverse(l2);

int carry = 0;
ListNode dummy = new ListNode(-1);

ListNode curr = dummy;

while(l1 != null || l2 != null){
int a = l1 == null ? 0 : l1.val;
int b = l2 == null ? 0 : l2.val;

curr.next = new ListNode((a + b + carry)%10);

carry = (a + b + carry)/10;

curr = curr.next;

if(l1 != null){
l1 = l1.next;
}

if(l2 != null){
l2 = l2.next;
}
}

if(carry > 0){
curr.next = new ListNode(carry);
}

return reverse(dummy.next);
}
}```

## Complexity Analysis for Add Two Numbers II Leetcode Solution

### Time Complexity

The time complexity of the above code is O(N + M) since we traverse both the linked lists in linear time, and added the two numbers represented as the linked list.

### Space Complexity

The space complexity of the above code is O(max(N, M)).

Translate »