Solving LeetCode Problem #2: Add Two Numbers

Problem Statement

LeetCode problem #2 - Add Two Numbers requires us to add two non-empty linked lists representing non-negative integers. The digits are stored in reverse order, and each node contains a single digit. We need to return the sum as a linked list.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Approach 1: Iterative Solution

A straightforward approach is to traverse both lists while maintaining a carry. We sum corresponding digits from both lists and update the carry accordingly.

Implementation:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)
    current = dummy
    carry = 0

    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0

        total = val1 + val2 + carry
        carry, digit = divmod(total, 10)
        current.next = ListNode(digit)
        current = current.next

        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None

    return dummy.next

Approach 2: Recursive Solution

We can also use recursion to process each node while carrying forward the sum.

Implementation:

def addTwoNumbersRecursive(l1: ListNode, l2: ListNode, carry=0) -> ListNode:
    if not l1 and not l2 and not carry:
        return None

    val1 = l1.val if l1 else 0
    val2 = l2.val if l2 else 0
    total = val1 + val2 + carry
    carry, digit = divmod(total, 10)

    result = ListNode(digit)
    result.next = addTwoNumbersRecursive(l1.next if l1 else None, l2.next if l2 else None, carry)

    return result

Complexity Analysis

• Time Complexity: (O(\max(N, M))) where (N) and (M) are the lengths of the two lists.
• Space Complexity: (O(\max(N, M))) for the recursive approach due to call stack depth, but (O(1)) for the iterative approach.

Edge Cases Considered

1. Different Lengths: One list is longer than the other.
2. Carry Over: The sum at a node results in a carry.
3. All Zeros: Both lists contain only zeros.
4. Single Digit Lists: Lists contain only one node.

Conclusion

The iterative approach is efficient and easy to implement, while the recursive approach provides a more elegant solution. Choosing between them depends on readability preferences and stack depth considerations.