Solution Explanation for LeetCode 445: Add Two Numbers II

This problem asks to add two numbers represented as linked lists where the most significant digit is at the head. We cannot directly add them like we would with integers because the lists are reversed. The most efficient solution uses stacks.

Approach:

1. Convert Linked Lists to Stacks: Iterate through both linked lists and push each node's value onto separate stacks. The stack structure naturally reverses the order of digits, aligning them for addition.

2. Add Numbers from Stacks: Pop values from both stacks simultaneously. Add the popped values along with any carry from the previous addition. The result is the sum of digits at that position.

3. Create Result Linked List: Construct the result linked list starting from the least significant digit (obtained last from the stacks). Use a dummy node to simplify the process of creating the list.

4. Handle Carry: Keep track of the carry value. If the sum of two digits exceeds 9, the carry becomes 1; otherwise, it's 0.

Code Explanation (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]:
        s1, s2 = [], []
        while l1:  # Push values from l1 onto stack s1
            s1.append(l1.val)
            l1 = l1.next
        while l2:  # Push values from l2 onto stack s2
            s2.append(l2.val)
            l2 = l2.next
        dummy = ListNode()  # Dummy node simplifies list creation
        carry = 0
        while s1 or s2 or carry:  # Continue until both stacks are empty and carry is 0
            s = (0 if not s1 else s1.pop()) + (0 if not s2 else s2.pop()) + carry
            carry, val = divmod(s, 10)  # Calculate carry and digit value
            dummy.next = ListNode(val, dummy.next) # Prepend the digit to the result list
        return dummy.next # Return the result list (excluding the dummy node)

Time Complexity: O(max(m, n)), where m and n are the lengths of the input linked lists. We iterate through each list once to create the stacks and then iterate until the stacks are empty and carry is 0.

Space Complexity: O(max(m, n)). The space used is dominated by the stacks, whose sizes are proportional to the lengths of the input lists.

Other Languages:

The solutions in Java, C++, Go, TypeScript, and Rust follow the same approach with minor syntactic differences. The core logic of using stacks for digit addition and building the result list remains consistent. They all have the same time and space complexity as the Python solution.

Note: A solution without reversing the lists is significantly more complex and less efficient. The stack-based approach presented here provides a clean and efficient solution to the problem.