LeetCode 445 - Add Two Numbers II

LeetCode Problem 445

Difficulty: 🟡 Medium
Topics: Linked List, Math, Stack

Solution

Problem Understanding

The problem gives us two non-empty singly linked lists where each node stores a single digit of a non-negative integer. Unlike the classic "Add Two Numbers" problem, the digits are stored in forward order, meaning the most significant digit appears first.

For example, the linked list:

7 -> 2 -> 4 -> 3

represents the integer 7243.

The task is to add the two represented integers together and return the result as a linked list in the same forward-order format.

The key challenge comes from the fact that addition naturally proceeds from right to left, starting with the least significant digit. However, singly linked lists only allow traversal from left to right. Because the digits are stored from most significant to least significant, we cannot directly process the lists in the order they are given.

The constraints are relatively small, with at most 100 nodes per list, so efficiency is not a severe concern in terms of raw performance. However, the follow-up explicitly asks whether we can solve the problem without reversing the input lists, which strongly hints that the intended solution should preserve the original list structure.

Several edge cases are important to consider:

• The two lists may have different lengths.
• A carry may propagate all the way to a new leading digit, such as 999 + 1 = 1000.
• One or both lists may represent zero.
• The lists do not contain leading zeros, which simplifies handling of the most significant digit.

Because the digits are stored in forward order, we need a strategy that allows us to process digits from the back without modifying the input lists.

Approaches

Brute Force Approach

A straightforward solution is to convert both linked lists into integers, add them together, and then convert the resulting sum back into a linked list.

The process would look like this:

1. Traverse the first linked list and construct the integer digit by digit.
2. Traverse the second linked list and do the same.
3. Add the two integers.
4. Convert the resulting integer back into a linked list.

This approach works conceptually because linked lists are simply another representation of integers.

However, this solution has several drawbacks. In many programming languages, integers may overflow for very large inputs. While Python supports arbitrarily large integers, relying on built-in big integer support is generally discouraged in interview settings because it bypasses the core linked list manipulation challenge.

Additionally, this approach does not address the follow-up requirement of operating directly on the linked lists without converting them into integers.

Optimal Approach

The key observation is that addition must proceed from the least significant digit, but the linked lists provide digits from most significant to least significant.

A stack solves this mismatch naturally.

By pushing all digits from each linked list onto separate stacks, we reverse the processing order implicitly. The top of each stack becomes the least significant remaining digit, allowing us to simulate standard elementary-school addition from right to left.

At each step:

• Pop one digit from each stack if available.
• Add them together along with the carry.
• Create a new node containing the current digit.
• Insert the node at the front of the result list.

Building the result from the front avoids needing a second reversal at the end.

This solution preserves the original lists, handles arbitrary lengths cleanly, and naturally supports carry propagation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n + m)	O(n + m)	Converts lists to integers and back
Optimal	O(n + m)	O(n + m)	Uses stacks to process digits from least significant to most significant

Algorithm Walkthrough

1. Create two empty stacks.

The stacks will store the digits from the two linked lists. Since stacks are Last-In-First-Out structures, pushing digits in forward order allows us to later process them in reverse order. 2. Traverse the first linked list and push each digit onto the first stack.

For the list 7 -> 2 -> 4 -> 3, the stack becomes:

[7, 2, 4, 3]

The top of the stack is 3, which is the least significant digit. 3. Traverse the second linked list and push each digit onto the second stack.

This prepares both numbers for right-to-left addition. 4. Initialize a variable called carry to 0.

This stores overflow from the previous digit addition. 5. Initialize the result list head as None.

We will construct the answer incrementally by inserting nodes at the front. 6. While either stack still contains digits or there is a remaining carry:

1. Pop the top digit from each stack if available.
2. Add both digits and the carry together.
3. Compute:

• digit = total % 10
• carry = total // 10

4. Create a new node containing digit.
5. Insert this node at the front of the result list.

Front insertion is critical because we are processing digits from least significant to most significant. 7. Return the head of the result list.

Why it works

The algorithm works because stacks reverse the traversal order of the linked lists. This allows us to process digits exactly as standard addition requires, from least significant to most significant.

At every iteration, the algorithm maintains the invariant that the partially constructed result list already represents the correct sum of all processed lower-order digits. Carry propagation ensures correctness across digit boundaries. Since each newly computed digit is inserted at the front, the final linked list appears in the required forward order.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import Optional

class Solution:
    def addTwoNumbers(
        self,
        l1: Optional[ListNode],
        l2: Optional[ListNode]
    ) -> Optional[ListNode]:

        stack1 = []
        stack2 = []

        current = l1
        while current:
            stack1.append(current.val)
            current = current.next

        current = l2
        while current:
            stack2.append(current.val)
            current = current.next

        carry = 0
        head = None

        while stack1 or stack2 or carry:
            total = carry

            if stack1:
                total += stack1.pop()

            if stack2:
                total += stack2.pop()

            digit = total % 10
            carry = total // 10

            new_node = ListNode(digit)
            new_node.next = head
            head = new_node

        return head

The implementation begins by traversing both linked lists and pushing their digits into stacks. This transforms the forward-order representation into a structure that allows reverse-order processing.

The carry variable stores overflow between digit additions. During each iteration, the algorithm pops one digit from each stack if available, adds them together with the carry, and computes the resulting digit and updated carry.

A new node is then inserted at the front of the result list. This front insertion is important because digits are processed from least significant to most significant, but the final output must remain in forward order.

The loop continues as long as either stack still contains digits or a carry remains. This naturally handles cases where the final addition produces an extra leading digit.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    stack1 := []int{}
    stack2 := []int{}

    for l1 != nil {
        stack1 = append(stack1, l1.Val)
        l1 = l1.Next
    }

    for l2 != nil {
        stack2 = append(stack2, l2.Val)
        l2 = l2.Next
    }

    carry := 0
    var head *ListNode = nil

    for len(stack1) > 0 || len(stack2) > 0 || carry > 0 {
        total := carry

        if len(stack1) > 0 {
            total += stack1[len(stack1)-1]
            stack1 = stack1[:len(stack1)-1]
        }

        if len(stack2) > 0 {
            total += stack2[len(stack2)-1]
            stack2 = stack2[:len(stack2)-1]
        }

        digit := total % 10
        carry = total / 10

        newNode := &ListNode{
            Val:  digit,
            Next: head,
        }

        head = newNode
    }

    return head
}

The Go implementation follows the same overall logic as the Python version. Since Go does not provide a built-in stack type, slices are used as stacks. The last element of the slice represents the top of the stack.

Unlike Python, Go distinguishes explicitly between nil pointers and valid nodes, so the result list head is initialized as nil.

Integer overflow is not a concern because each digit addition involves only small values between 0 and 9, plus a carry of at most 1.

Worked Examples

Example 1

Input:

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

Initial stacks:

Stack 1	Stack 2
[7,2,4,3]	[5,6,4]

Processing steps:

Step	Pop 1	Pop 2	Carry In	Total	Digit	Carry Out	Result List
1	3	4	0	7	7	0	[7]
2	4	6	0	10	0	1	[0,7]
3	2	5	1	8	8	0	[8,0,7]
4	7	-	0	7	7	0	[7,8,0,7]

Final output:

[7,8,0,7]

Example 2

Input:

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

Initial stacks:

Stack 1	Stack 2
[2,4,3]	[5,6,4]

Processing:

Step	Pop 1	Pop 2	Carry In	Total	Digit	Carry Out	Result List
1	3	4	0	7	7	0	[7]
2	4	6	0	10	0	1	[0,7]
3	2	5	1	8	8	0	[8,0,7]

Final output:

[8,0,7]

Example 3

Input:

l1 = [0]
l2 = [0]

Initial stacks:

Stack 1	Stack 2
[0]	[0]

Processing:

Step	Pop 1	Pop 2	Carry In	Total	Digit	Carry Out	Result List
1	0	0	0	0	0	0	[0]

Final output:

[0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Each node is visited once and each stack operation is O(1)
Space	O(n + m)	The stacks store all digits from both linked lists

The algorithm traverses each linked list exactly once to build the stacks, then processes each digit once more during addition. Since each stack push and pop operation is constant time, the total runtime is linear in the combined length of the lists.

The extra space usage comes entirely from the two stacks, which together store every digit from the input lists.

Test Cases

# Helper utilities for testing

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

def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

def list_to_array(node):
    result = []

    while node:
        result.append(node.val)
        node = node.next

    return result

solution = Solution()

# Example 1
l1 = build_list([7, 2, 4, 3])
l2 = build_list([5, 6, 4])
assert list_to_array(solution.addTwoNumbers(l1, l2)) == [7, 8, 0, 7]  # different lengths

# Example 2
l1 = build_list([2, 4, 3])
l2 = build_list([5, 6, 4])
assert list_to_array(solution.addTwoNumbers(l1, l2)) == [8, 0, 7]  # carry in middle

# Example 3
l1 = build_list([0])
l2 = build_list([0])
assert list_to_array(solution.addTwoNumbers(l1, l2)) == [0]  # both zero

# Carry creates new leading digit
l1 = build_list([9, 9, 9])
l2 = build_list([1])
assert list_to_array(solution.addTwoNumbers(l1, l2)) == [1, 0, 0, 0]  # final carry

# Different lengths without carry
l1 = build_list([1, 2, 3, 4])
l2 = build_list([5])
assert list_to_array(solution.addTwoNumbers(l1, l2)) == [1, 2, 3, 9]  # uneven lengths

# Long carry chain
l1 = build_list([9, 9, 9, 9])
l2 = build_list([9, 9, 9, 9])
assert list_to_array(solution.addTwoNumbers(l1, l2)) == [1, 9, 9, 9, 8]  # repeated carry propagation

# One list much longer
l1 = build_list([1])
l2 = build_list([9, 9, 9, 9, 9])
assert list_to_array(solution.addTwoNumbers(l1, l2)) == [1, 0, 0, 0, 0]  # carry through longer list

Test	Why
[7,2,4,3] + [5,6,4]	Validates standard operation with unequal lengths
[2,4,3] + [5,6,4]	Validates carry handling in the middle
[0] + [0]	Validates smallest possible input
[9,9,9] + [1]	Validates creation of a new leading digit
[1,2,3,4] + [5]	Validates unequal lengths without cascading carry
[9,9,9,9] + [9,9,9,9]	Validates repeated carry propagation
[1] + [9,9,9,9,9]	Validates carry propagation across a much longer list

Edge Cases

One important edge case occurs when the final addition produces a new leading digit. For example, adding 999 + 1 results in 1000. A naive implementation might stop processing once both input lists are exhausted and forget to handle the remaining carry. This implementation avoids that bug by continuing the loop while carry is nonzero.

Another important edge case involves lists of different lengths. Since the two linked lists are not guaranteed to contain the same number of digits, one stack may become empty before the other. The algorithm handles this cleanly by only popping from a stack if it still contains values. Missing digits are effectively treated as zero.

A third edge case is when both inputs represent zero. Some implementations accidentally return an empty list in this situation. Here, the algorithm correctly creates a node containing 0 because the loop still executes once when both stacks contain a zero digit.

A subtle edge case involves long chains of carry propagation, such as 9999 + 9999. Incorrect implementations may mishandle carry updates across multiple iterations. This algorithm recomputes the carry independently at every step using integer division, ensuring that carry propagation remains correct regardless of chain length.