Add Two numbers

2.Add Two Numbers

Linked List

Math

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.

Example:

Input:

l1 = [2,4,3], l2 = [5,6,4]

→

Output:

[7,0,8]

Java Solution:

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), curr = dummy;
    int carry = 0, sum = 0;

    while (l1 != null || l2 != null) {
        sum = carry;
        curr.next = new ListNode(0);
        curr = curr.next;

        if (l1 != null) { sum += l1.val; l1 = l1.next; }
        if (l2 != null) { sum += l2.val; l2 = l2.next; }

        carry = sum >= 10 ? 1 : 0;
        sum = sum % 10;

        curr.val = sum;
    }

    if (carry == 1) curr.next = new ListNode(carry);

    return dummy.next;
}

Python Solution:

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)
    curr = dummy
    carry = 0
    
    while l1 or l2:
        sum_val = carry
        curr.next = ListNode(0)
        curr = curr.next
        
        if l1:
            sum_val += l1.val
            l1 = l1.next
        if l2:
            sum_val += l2.val
            l2 = l2.next
            
        carry = 1 if sum_val >= 10 else 0
        sum_val = sum_val % 10
        
        curr.val = sum_val
        
    if carry == 1:
        curr.next = ListNode(carry)
        
    return dummy.next

C++ Solution:

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* curr = dummy;
        int carry = 0, sum = 0;
        
        while(l1 || l2) {
            sum = carry;
            curr->next = new ListNode(0);
            curr = curr->next;
            
            if(l1) { sum += l1->val; l1 = l1->next; }
            if(l2) { sum += l2->val; l2 = l2->next; }
            
            carry = sum >= 10 ? 1 : 0;
            sum = sum % 10;
            
            curr->val = sum;
        }
        
        if(carry == 1)
            curr->next = new ListNode(carry);
        
        return dummy->next;
    }
};

Complexity:

Time: O(max(N,M)) where N and M are lengths of input lists
Space: O(max(N,M)) to store the result