In this post, we are going to solve the 445. Add Two Numbers 2 problem of Leetcode. This problem 445. Add Two Numbers 2 is a Leetcode medium level problem. Let’s see the code, 445. Add Two Numbers 2 – Leetcode Solution.

Problem

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

Example 2 :

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

Example 3 :

Input: l1 = [0], l2 = [0]
Output: [0]

Constraints

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros

Now, let’s see the code of 445. Add Two Numbers 2 – Leetcode Solution.

Add Two Numbers 2 – Leetcode Solution

445. Add Two Numbers 2 – Solution in Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    
    public ListNode reverseList(ListNode root){
        if(root == null || root.next == null) return root;
        
        ListNode curr = root, prev = null;
        while( curr != null){
            ListNode forw = curr.next;
            curr.next = prev;
            prev = curr;
            curr = forw;
        }
        return prev;
    }
    
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       
        
        if(l1 == null || l2 == null){
            return l1 == null ? l2 : l1;
        }
        
        ListNode revL1 = reverseList(l1);
        ListNode revL2 = reverseList(l2);
        ListNode result = new ListNode();
        ListNode ans = result;
        int carry=0;
        while(revL1 != null && revL2 != null){
            
            int sum = carry + revL1.val + revL2.val;
            int digit = sum%10;
            carry = sum/10;
            
            revL1 = revL1.next;
            revL2 = revL2.next;
            
           result.next = new ListNode(digit);   
            result = result.next;
        }
        
        while(revL1 != null){
            int sum = carry + revL1.val;
            int digit = sum%10;
            carry = sum/10;
            result.next = new ListNode(digit);
            revL1 = revL1.next;
            result = result.next;
        } 
        
        while(revL2 != null){
            int sum = carry + revL2.val;
            int digit = sum%10;
            carry = sum/10;
            result.next = new ListNode(digit);
            revL2 = revL2.next;
            result = result.next;
        } 
        
        if(carry != 0){
            result.next = new ListNode(carry);
        }
        
        return reverseList(ans.next);
        
    }
}

445. Add Two Numbers 2 – Solution in C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    
    ListNode* reverse(ListNode* head)
    {
        if(head == NULL || head->next == NULL) return head;
        ListNode* cur = head, * prev = NULL, *forw = head;
        while(cur != NULL){
            forw = forw->next;
            cur->next = prev;
            prev = cur;
            cur = forw;
        }
        return prev;
    }
    
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if(l1 == NULL || l2 == NULL) return l1==NULL?l2:l1;
        
        l1 = reverse(l1);
        l2 = reverse(l2);

        ListNode* head = new ListNode(0);
        ListNode* itr = head;
        int carry = 0;
        while(l1 != NULL || l2 != NULL || carry != 0){
            int val = carry;

            if(l1!= NULL){
                val+=l1->val;
                l1 = l1->next;
            }
            if(l2!=NULL){
                val+=l2->val;
                l2 = l2->next;
            }
            itr->next = new ListNode();
            itr = itr->next;
            itr->val = val%10;
            carry = val/10;   
        }
        
        return reverse(head->next);
    }
};

445. Add Two Numbers 2 – Solution in Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        first, sec = self.reverse(l1), self.reverse(l2)
        if self.getLength(first) > self.getLength(sec):
            return self.reverse(self.addList(first, sec))
        return self.reverse(self.addList(sec, first))
        
    
    def addList(self, A, B):
        head = A
        carry = 0
        while A or B:
            Aval = A.val 
            Bval = B.val if B else 0
            curSum = Aval + Bval + carry
            
            A.val = curSum % 10
            carry = curSum // 10
            prev = A
            A, B = A.next , B.next if B else None
        
        if carry:
            prev.next = ListNode(carry)
        return head
        
    
    def reverse(self, head):
        prev, cur = None, head
        
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        
        return prev
    
    
    def getLength(self, head):
        l = 0
        while head:
            head = head.next
            l += 1
        return l
        

Note: This problem 445. Add Two Numbers 2 is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.