LeetCode 445: Add Two Numbers II

Problem Restatement

We are given two non-empty linked lists.

Each linked list represents a non-negative integer.

Each node stores one digit, and the digits are stored in forward order. That means the most significant digit comes first.

For example:

7 -> 2 -> 4 -> 3

represents:

7243

We need to add the two numbers and return the sum as a linked list, also in forward order.

The numbers have no leading zero, except for the number 0 itself. The official problem asks us to return the sum as a linked list with the most significant digit first.

Input and Output

The node class is usually:

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

Examples

Example 1:

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

These represent:

7243 + 564 = 7807

So the output is:

[7, 8, 0, 7]

Example 2:

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

These represent:

243 + 564 = 807

Output:

[8, 0, 7]

Example 3:

l1 = [0]
l2 = [0]

Output:

[0]

First Thought: Reverse the Lists

If the digits were stored backward, addition would be easy.

We could start from the ones place, add digit by digit, and carry as needed.

But here the lists begin with the largest place value.

One option is:

1. Reverse both input lists.
2. Add them normally.
3. Reverse the result.

This works, but it modifies the input lists unless we carefully copy them first.

A cleaner solution is to use stacks.

Key Insight

A stack lets us read the linked list from left to right, then process it from right to left.

For example:

l1 = 7 -> 2 -> 4 -> 3

After pushing values into a stack:

[7, 2, 4, 3]

Popping gives:

3, 4, 2, 7

That is exactly the order needed for manual addition.

We use two stacks:

Then we repeatedly pop digits, add them with carry, and build the result by inserting each new digit at the front.

Algorithm

Push all digits from l1 into stack1.

Push all digits from l2 into stack2.

Initialize:

carry = 0
head = None

While either stack still has digits, or carry is non-zero:

1. Start with total = carry.
2. If stack1 is not empty, pop and add its top digit.
3. If stack2 is not empty, pop and add its top digit.
4. The new digit is:

total % 10

5. The new carry is:

total // 10

6. Create a new node for the digit.
7. Insert it before the current result head.

Return head.

Correctness

The stacks store the digits of each input number in reverse processing order. Therefore, each pop gives the next digit from least significant to most significant.

At each step, the algorithm adds the current digit from l1, the current digit from l2, and the carry from the previous lower-place addition. This is exactly the standard column addition rule.

The digit stored in the result node is total % 10, which is the correct digit for the current place. The carry becomes total // 10, which is the amount that must be added to the next higher place.

Because we process digits from least significant to most significant, each new result digit belongs before the already-built result list. Inserting each new node at the front keeps the final linked list in forward order.

When both stacks are empty and carry is zero, all digits and carries have been processed. The returned list therefore represents the exact sum of the two input numbers.

Complexity

Here, m and n are the lengths of the two linked lists.

The output list is not counted as extra working space.

Implementation

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

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

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

        carry = 0
        head = None

        while stack1 or stack2 or carry:
            total = carry

            if stack1:
                total += stack1.pop()

            if stack2:
                total += stack2.pop()

            carry = total // 10
            digit = total % 10

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

        return head

Code Explanation

First, we collect the digits:

stack1 = []
stack2 = []

Each linked list is scanned from head to tail.

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

After this, the top of the stack is the least significant digit.

The addition loop continues while there is still work:

while stack1 or stack2 or carry:

We begin each column with the previous carry:

total = carry

Then we add one digit from each stack if available:

if stack1:
    total += stack1.pop()

if stack2:
    total += stack2.pop()

The carry and output digit are computed by:

carry = total // 10
digit = total % 10

The new node is inserted at the front:

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

This keeps the result in most-significant-first order.

Testing

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

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

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

    return dummy.next

def to_list(head):
    values = []

    while head:
        values.append(head.val)
        head = head.next

    return values

def run_tests():
    s = Solution()

    assert to_list(
        s.addTwoNumbers(
            build_list([7, 2, 4, 3]),
            build_list([5, 6, 4]),
        )
    ) == [7, 8, 0, 7]

    assert to_list(
        s.addTwoNumbers(
            build_list([2, 4, 3]),
            build_list([5, 6, 4]),
        )
    ) == [8, 0, 7]

    assert to_list(
        s.addTwoNumbers(
            build_list([0]),
            build_list([0]),
        )
    ) == [0]

    assert to_list(
        s.addTwoNumbers(
            build_list([9, 9, 9]),
            build_list([1]),
        )
    ) == [1, 0, 0, 0]

    assert to_list(
        s.addTwoNumbers(
            build_list([1]),
            build_list([9, 9, 9]),
        )
    ) == [1, 0, 0, 0]

    print("all tests passed")

run_tests()

Test meaning: