445. Add Two Numbers II

Reformulated question¶

Add two non-empty linked lists where each node is one digit and digits are stored most-significant first; return the sum in the same format, without leading zeros.

Example:

l1: 7 -> 2 -> 4 -> 3
l2: 5 -> 6 -> 4
out: 7 -> 8 -> 0 -> 7   # 7243 + 564 = 7807

Key trick¶

Use stacks or recurse from the tail so you can add digits right-to-left while keeping the output in forward order.

Trap¶

Adding only while both lists exist and then appending the rest is wrong because carry must keep propagating.
Reversing inputs is fine for the basic problem, but the follow-up asks to avoid it.
Converting to Python integers works here in Python, but it is usually not the intended linked-list technique.

Why this question is interesting?¶

It tests how to simulate grade-school addition when the list order is the opposite of the natural processing order.

Solve the problem with idiomatic python¶

from typing import Optional

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # Push digits so we can add from least significant to most significant
        s1, s2 = [], []

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

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

        carry = 0
        head = None

        # Build result from back to front by prepending nodes
        while s1 or s2 or carry:
            total = carry

            if s1:
                total += s1.pop()

            if s2:
                total += s2.pop()

            carry, digit = divmod(total, 10)
            head = ListNode(digit, head)

        return head

Pytest test¶

import pytest
from utils import list_build, list_to_python_list

@pytest.mark.parametrize(
    ("a", "b", "expected"),
    [
        ([7, 2, 4, 3], [5, 6, 4], [7, 8, 0, 7]),
        ([2, 4, 3], [5, 6, 4], [8, 0, 7]),
        ([0], [0], [0]),
        ([9], [1], [1, 0]),
        ([9, 9, 9], [1], [1, 0, 0, 0]),
        ([1], [9, 9, 9], [1, 0, 0, 0]),
        ([6, 1, 7], [2, 9, 5], [9, 1, 2]),
        ([1, 0, 0, 0], [9, 9, 9], [1, 9, 9, 9]),
    ],
)
def test_add_two_numbers_ii(a, b, expected):
    got = Solution().addTwoNumbers(list_build(a), list_build(b))
    assert list_to_python_list(got) == expected

Comment my solution¶

Your first reverse-based attempt fails because after the common part ends, it attaches the remaining nodes directly without adding the carry through them.
It also forgets to append a final carry like 999 + 1 -> 1000.
Your integer-conversion solution passes in Python and is short, but interviewers often prefer a true linked-list solution because it matches the follow-up idea and avoids relying on big integers.

# WRONG - Doesn't pass leetcode tests
# First attempt (reversing lists)
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        def reverse_list(l):
            prev = None
            cur = l

            while cur:
                nxt = cur.next      # save tail before rewiring
                cur.next = prev     # reverse pointer
                prev = cur          # grow reversed prefix
                cur = nxt           # continue forward

            return prev

        l1 = reverse_list(l1)
        l2 = reverse_list(l2)

        sum = ListNode()
        dummy = sum
        decimal = 0
        while l1 and l2:
            v1, v2 = l1.val, l2.val
            l1, l2 = l1.next, l2.next
            n = v1 + v2 + decimal
            new_decimal = n // 10
            digit = n % 10
            sum.next = ListNode(digit)
            sum = sum.next
            decimal = new_decimal
        if l1:
            sum.next = l1
        if l2:
            sum.next = l2
        return reverse_list(dummy.next)

# OK - Pass leetcode test
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        def reverse_list(l):
            prev = None
            cur = l

            while cur:
                nxt = cur.next      # save tail before rewiring
                cur.next = prev     # reverse pointer
                prev = cur          # grow reversed prefix
                cur = nxt           # continue forward

            return prev

        num1 = 0
        while l1:
            num1 = num1 * 10 + l1.val
            l1 = l1.next
        num2 = 0
        while l2:
            num2 = num2 * 10 + l2.val
            l2 = l2.next

        sum = num1 + num2

        digit = sum % 10
        sum = sum // 10
        sum_list = ListNode(digit)
        head_sum = sum_list

        while sum:
            digit = sum % 10
            sum = sum // 10
            sum_list.next = ListNode(digit)
            sum_list = sum_list.next

        return reverse_list(head_sum)

# OK - Written after reading AI comments
class Solution:
    def addTwoNumbers(self, l1, l2) -> Optional[ListNode]:
        stack1 = []
        stack2 = []
        while l1:
            stack1.append(l1.val)
            l1 = l1.next
        while l2:
            stack2.append(l2.val)
            l2 = l2.next
        stack_sum = []
        dec = 0
        while stack1 or stack2 or dec:
            d1 = stack1.pop() if stack1 else 0
            d2 = stack2.pop() if stack2 else 0
            n = d1 + d2 + dec
            dec = n // 10
            digit = n % 10
            stack_sum.append(digit)
        sum = ListNode()
        dummy = sum
        while stack_sum:
            sum.next = ListNode(stack_sum.pop())
            sum = sum.next

        return dummy.next

divmod(32, 10) # (3, 2)
divmod(8, 10)  # (0, 8)
divmod(3, 2)   # (1, 1)
divmod(2, 2)   # (1, 0)