Add Two Numbers II [Linked List]

XXX. Add Two Numbers (Non-Reversed)

Linked List

Recursion

Math

Problem Statement:

Given two non-empty linked lists representing two non-negative integers, where the digits are stored in their normal order, add the two numbers and return the result as a linked list.

The linked lists represent the numbers such that each node contains a single digit. You cannot reverse the linked lists. Handle any carry-over that arises from adding two digits.

Algorithm:

1. Calculate the lengths of both linked lists.
2. Ensure the first linked list is longer than or equal to the second.
3. Use recursion to add the digits of both lists, respecting any offset due to differing lengths.
4. Handle carry-over after adding digits:
• If the sum exceeds 9, propagate the carry to the previous node.
5. Return the final linked list, including handling any carry that arises at the most significant digit.

Complexity:

Time Complexity: O(n), where n is the length of the longer linked list.
Space Complexity: O(h), where h is the height of the recursion stack.

Java Implementation:

// Main function to add two numbers represented by linked lists
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    // Get the lengths of both linked lists
    int size1 = getLength(l1); // Length of the first list
    int size2 = getLength(l2); // Length of the second list

    // Create a dummy head node with a value of 1 (to handle carry propagation)
    ListNode head = new ListNode(1);

    // Ensure l1 is the longer list by comparing their lengths
    head.next = size1 < size2 ? helper(l2, l1, size2 - size1) : helper(l1, l2, size1 - size2);

    // Check if the most significant digit has a carry
    if (head.next.val > 9) {
        // If carry exists, adjust the value and return the dummy head
        head.next.val %= 10;
        return head;
    }
    // If no carry, skip the dummy node and return the actual result
    return head.next;
}

// Recursive helper function to perform digit-wise addition
public ListNode helper(ListNode l1, ListNode l2, int offset) {
    // Base case: if l1 is null, return null (end of recursion)
    if (l1 == null) return null;

    // Add the current digits
    // If offset > 0, only l1 contributes to the result until the lists align
    ListNode result = offset == 0 ? new ListNode(l1.val + l2.val) : new ListNode(l1.val);

    // Recursive call to process the next digits
    // If offset == 0, both lists are processed simultaneously
    ListNode post = offset == 0 ? helper(l1.next, l2.next, 0) : helper(l1.next, l2, offset - 1);

    // Handle carry-over from the next digit
    if (post != null && post.val > 9) {
        result.val += 1; // Add carry to the current digit
        post.val %= 10;  // Reduce the carried digit to a single digit
    }

    // Link the current node to the next result node
    result.next = post;
    return result;
}

// Utility function to calculate the length of a linked list
public int getLength(ListNode l) {
    int count = 0;
    while (l != null) { // Traverse through the list
        l = l.next; // Move to the next node
        count++;    // Increment the count
    }
    return count; // Return the total length of the list
}

Python Implementation:

class Solution:
    def addTwoNumbers(self, l1, l2):
        # Calculate the lengths of both linked lists
        size1, size2 = self.getLength(l1), self.getLength(l2)

        # Create a dummy head node to manage carry propagation
        head = ListNode(1)

        # Ensure l1 is the longer list
        head.next = self.helper(l2, l1, size2 - size1) if size1 < size2 else self.helper(l1, l2, size1 - size2)

        # Handle carry in the most significant digit
        if head.next.val > 9:
            head.next.val %= 10
            return head
        return head.next

    def helper(self, l1, l2, offset):
        # Base case: end of the list
        if not l1:
            return None

        # Add the digits of the current nodes
        result = ListNode(l1.val + l2.val if offset == 0 else l1.val)

        # Recursive call for the next nodes
        post = self.helper(l1.next, l2.next, 0) if offset == 0 else self.helper(l1.next, l2, offset - 1)

        # Handle carry from the next digit
        if post and post.val > 9:
            result.val += 1 # Add carry to the current node
            post.val %= 10  # Reduce the carried digit to a single digit

        # Link the current node to the next result node
        result.next = post
        return result

    def getLength(self, l):
        count = 0
        while l: # Traverse through the list
            l = l.next # Move to the next node
            count += 1 # Increment the count
        return count # Return the total length of the list

C++ Implementation:

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        // Calculate the lengths of both linked lists
        int size1 = getLength(l1), size2 = getLength(l2);

        // Create a dummy head node to manage carry propagation
        ListNode* head = new ListNode(1);

        // Ensure l1 is the longer list
        head->next = size1 < size2 ? helper(l2, l1, size2 - size1) : helper(l1, l2, size1 - size2);

        // Handle carry in the most significant digit
        if (head->next->val > 9) {
            head->next->val %= 10;
            return head;
        }
        return head->next;
    }

private:
    ListNode* helper(ListNode* l1, ListNode* l2, int offset) {
        // Base case: end of the list
        if (!l1) return nullptr;

        // Add the digits of the current nodes
        ListNode* result = offset == 0 ? new ListNode(l1->val + l2->val) : new ListNode(l1->val);

        // Recursive call for the next nodes
        ListNode* post = offset == 0 ? helper(l1->next, l2->next, 0) : helper(l1->next, l2, offset - 1);

        // Handle carry from the next digit
        if (post && post->val > 9) {
            result->val += 1; // Add carry to the current node
            post->val %= 10;  // Reduce the carried digit to a single digit
        }

        // Link the current node to the next result node
        result->next = post;
        return result;
    }

    int getLength(ListNode* l) {
        int count = 0;
        while (l) { // Traverse through the list
            l = l->next; // Move to the next node
            count++;    // Increment the count
        }
        return count; // Return the total length of the list
    }
};