Problem Description

You are given two linked lists that represent non-negative integers. Each node in the linked list contains a single digit (0-9), and the digits are stored in most significant digit first order. This means the head of the linked list contains the leftmost (most significant) digit.

For example, the number 342 would be represented as: 3 -> 4 -> 2

Your task is to add these two numbers together and return the sum as a new linked list in the same format.

Key Points:

• Both linked lists are non-empty
• The numbers don't have leading zeros (except for the number 0 itself)
• You need to handle carries properly when digits sum to 10 or more
• The result should also be in most significant digit first order

Example: If you have:

• List 1: 7 -> 2 -> 4 -> 3 (representing 7243)
• List 2: 5 -> 6 -> 4 (representing 564)
• The sum is 7243 + 564 = 7807
• Result: 7 -> 8 -> 0 -> 7

The main challenge is that the digits are stored from left to right (most significant to least significant), but addition typically requires processing digits from right to left to handle carries properly. The solution uses stacks to reverse the order of digits, performs the addition with carry propagation, and builds the result linked list by inserting new nodes at the beginning to maintain the most significant digit first order.

Intuition

When we add two numbers manually on paper, we start from the rightmost digit (ones place) and work our way left, carrying over when needed. However, our linked lists present the digits in the opposite order - from left to right (most significant digit first).

The key insight is that we need to somehow reverse the order of processing. We have a few options:

1. Reverse the linked lists - We could reverse both lists, add them like in the standard "Add Two Numbers" problem, then reverse the result. This would work but requires multiple passes through the lists.

2. Use recursion - We could recursively traverse to the end of both lists and add while backtracking. However, this requires careful handling of different list lengths and can be complex.

3. Use stacks - This is the most elegant approach. Stacks naturally reverse the order of elements due to their Last-In-First-Out (LIFO) property.

By pushing all digits onto stacks, we can then pop from both stacks to get digits in reverse order (least significant first). This mimics how we naturally add numbers:

• Pop from both stacks to get the rightmost available digits
• Add them along with any carry from the previous addition
• Calculate the new carry and the digit to place in the result

The clever part of building the result is that instead of using another stack or reversing at the end, we can build the linked list in reverse by always inserting new nodes at the beginning. Each new node points to the previous head, naturally creating a list in the correct order.

For example, if we're building the number 807:

• First, we create node with value 7: 7 -> null
• Then insert 0 at the beginning: 0 -> 7 -> null
• Finally insert 8 at the beginning: 8 -> 0 -> 7 -> null

This approach elegantly handles all edge cases including different length numbers and carry propagation, while maintaining O(n + m) time complexity with a single pass after the initial stack population.

Solution Approach

Let's walk through the implementation step by step:

Step 1: Extract digits into stacks

s1, s2 = [], []
while l1:
    s1.append(l1.val)
    l1 = l1.next
while l2:
    s2.append(l2.val)
    l2 = l2.next

We traverse both linked lists and push each digit onto respective stacks. After this step:

• Stack s1 contains all digits from the first number
• Stack s2 contains all digits from the second number
• The top of each stack now has the least significant digit (rightmost)

Step 2: Initialize dummy node and carry

dummy = ListNode()
carry = 0

The dummy node serves as an anchor point to build our result list. We'll insert new nodes after it. The carry variable tracks overflow from digit addition.

Step 3: Process digits from least to most significant

while s1 or s2 or carry:
    s = (0 if not s1 else s1.pop()) + (0 if not s2 else s2.pop()) + carry
    carry, val = divmod(s, 10)
    dummy.next = ListNode(val, dummy.next)

This loop continues while:

• There are still digits in s1, OR
• There are still digits in s2, OR
• There's a carry to process

In each iteration:

1. Pop and sum: We pop from both stacks (or use 0 if a stack is empty) and add the carry
2. Calculate carry and digit: Using divmod(s, 10):
   • carry gets the tens digit (integer division by 10)
   • val gets the ones digit (remainder when divided by 10)
3. Insert at beginning: The key line dummy.next = ListNode(val, dummy.next) creates a new node with value val that points to the current dummy.next, then updates dummy.next to point to this new node

Building the result in correct order: The insertion pattern ensures correct digit order. For example, adding 342 + 465 = 807:

• First iteration: val=7, list becomes dummy -> 7 -> null
• Second iteration: val=0, list becomes dummy -> 0 -> 7 -> null
• Third iteration: val=8, list becomes dummy -> 8 -> 0 -> 7 -> null

Step 4: Return the result

return dummy.next

We return dummy.next which points to the head of our constructed list, skipping the dummy node itself.

This approach elegantly handles all cases including numbers of different lengths and final carry propagation, achieving O(n + m) time complexity where n and m are the lengths of the input lists.

Example Walkthrough

Let's walk through adding two numbers: 342 + 465 = 807

Input:

• List 1: 3 -> 4 -> 2 (representing 342)
• List 2: 4 -> 6 -> 5 (representing 465)

Step 1: Push digits onto stacks

Traverse List 1 and push to stack s1:

• Push 3: s1 = [3]
• Push 4: s1 = [3, 4]
• Push 2: s1 = [3, 4, 2]

Traverse List 2 and push to stack s2:

• Push 4: s2 = [4]
• Push 6: s2 = [4, 6]
• Push 5: s2 = [4, 6, 5]

Step 2: Add digits from right to left using stacks

Initialize: dummy -> null, carry = 0

Iteration 1: Process rightmost digits

• Pop from s1: 2, Pop from s2: 5
• Sum = 2 + 5 + 0 (carry) = 7
• carry = 7 ÷ 10 = 0, val = 7 % 10 = 7
• Insert 7 at beginning: dummy -> 7 -> null
• Remaining: s1 = [3, 4], s2 = [4, 6]

Iteration 2: Process middle digits

• Pop from s1: 4, Pop from s2: 6
• Sum = 4 + 6 + 0 (carry) = 10
• carry = 10 ÷ 10 = 1, val = 10 % 10 = 0
• Insert 0 at beginning: dummy -> 0 -> 7 -> null
• Remaining: s1 = [3], s2 = [4]

Iteration 3: Process leftmost digits

• Pop from s1: 3, Pop from s2: 4
• Sum = 3 + 4 + 1 (carry) = 8
• carry = 8 ÷ 10 = 0, val = 8 % 10 = 8
• Insert 8 at beginning: dummy -> 8 -> 0 -> 7 -> null
• Remaining: s1 = [], s2 = []

Iteration 4: Check termination

• Both stacks empty and carry = 0, so loop terminates

Step 3: Return result Return dummy.next which points to: 8 -> 0 -> 7

The final linked list correctly represents 807, which is the sum of 342 + 465.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m) where n is the length of linked list l1 and m is the length of linked list l2.

• Traversing l1 to populate stack s1: O(n)
• Traversing l2 to populate stack s2: O(m)
• The while loop for addition runs at most max(n, m) + 1 times (the +1 accounts for a potential final carry): O(max(n, m))
• Each iteration of the addition loop performs constant time operations: pop(), arithmetic operations, and creating a new node
• Total: O(n) + O(m) + O(max(n, m)) = O(n + m)

Space Complexity: O(n + m)

• Stack s1 stores all values from l1: O(n)
• Stack s2 stores all values from l2: O(m)
• The output linked list contains at most max(n, m) + 1 nodes: O(max(n, m))
• Additional variables (dummy, carry, s, val) use constant space: O(1)
• Total: O(n) + O(m) + O(max(n, m)) = O(n + m)

Common Pitfalls

Pitfall 1: Forgetting to Handle Final Carry

The Problem: A frequent mistake is forgetting that the final carry might create an additional digit in the result. For instance, when adding 999 + 1 = 1000, after processing all digits from both numbers, there's still a carry of 1 that needs to become the most significant digit.

Incorrect Implementation:

# WRONG: Only processes while stacks have elements
while stack1 or stack2:  # Missing carry condition!
    digit1 = stack1.pop() if stack1 else 0
    digit2 = stack2.pop() if stack2 else 0
    current_sum = digit1 + digit2 + carry
    carry, digit_value = divmod(current_sum, 10)
    dummy_head.next = ListNode(digit_value, dummy_head.next)

Why It Fails:

• Input: 9 -> 9 -> 9 + 1
• Expected: 1 -> 0 -> 0 -> 0
• Wrong Output: 0 -> 0 -> 0 (missing the leading 1)

Correct Solution: Always include carry in the loop condition:

while stack1 or stack2 or carry:  # Includes carry check
    # ... rest of the logic

Pitfall 2: Building Result List in Wrong Order

The Problem: Since we're processing digits from least significant to most significant (right to left), but need the result in most significant first order, incorrectly appending nodes to the end would reverse the result.

Incorrect Implementation:

# WRONG: Appending to the end of the list
result_head = ListNode(0)
current = result_head

while stack1 or stack2 or carry:
    # ... calculate digit_value
    current.next = ListNode(digit_value)  # Appends to end
    current = current.next

return result_head.next

Why It Fails:

• Input: 3 -> 4 -> 2 + 4 -> 6 -> 5
• Expected: 8 -> 0 -> 7
• Wrong Output: 7 -> 0 -> 8 (digits in reverse order)

Correct Solution: Insert each new node at the beginning (right after dummy):

dummy_head.next = ListNode(digit_value, dummy_head.next)

This prepends each digit, naturally building the number from right to left while maintaining most significant digit first order.

Pitfall 3: Modifying Input Lists

The Problem: Directly reversing or modifying the input linked lists instead of using auxiliary storage can cause issues if the input lists need to be preserved.

Incorrect Approach:

# WRONG: Reversing the input lists directly
def reverse_list(head):
    prev = None
    while head:
        next_node = head.next
        head.next = prev
        prev = head
        head = next_node
    return prev

l1_reversed = reverse_list(l1)  # Modifies original l1!
l2_reversed = reverse_list(l2)  # Modifies original l2!

Why It's Problematic:

• The original linked lists are destroyed
• If the caller needs the original lists intact, this causes unexpected behavior
• Makes the function have side effects

Correct Solution: Use stacks to store values without modifying the original lists:

stack1, stack2 = [], []
while l1:
    stack1.append(l1.val)  # Only reads values
    l1 = l1.next

This preserves the original linked list structure while still allowing reverse-order processing.