Add Two Numbers II Leetcode Solution

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* reverse(ListNode* head){
        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 {
    public ListNode reverse(ListNode head){
        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)).