2. Add Two Numbers

Reformulated question¶

Add two non-negative integers stored in reverse-order linked lists, and return the sum as a new reverse-order linked list.

Example:

l1 = 2 -> 4 -> 3
l2 = 5 -> 6 -> 4
sum = 7 -> 0 -> 8

This means 342 + 465 = 807.

Key trick¶

Traverse both lists at the same time, keep a carry, and use a dummy head to build the result list node by node.

Trap¶

Forgetting the final carry.
Stopping when one list ends instead of continuing with the other.
Reusing nodes from the input lists and accidentally mutating them.
Treating the digits as normal order instead of reverse order.

Why is this question interesting?¶

It tests linked-list traversal, carry handling, and clean construction of a new list in one of the simplest but most common interview patterns.

Solution¶

from typing import Optional

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # Dummy head makes list construction simpler.
        dummy = ListNode(0)
        tail = dummy
        carry = 0

        # Keep going while we still have digits or a carry.
        while l1 or l2 or carry:
            total = carry

            if l1:
                total += l1.val
                l1 = l1.next

            if l2:
                total += l2.val
                l2 = l2.next

            carry, digit = divmod(total, 10)
            tail.next = ListNode(digit)
            tail = tail.next

        return dummy.next

Pytest test cases¶

import pytest

from utils import list_build, list_to_python_list


@pytest.mark.parametrize(
    "l1,l2,expected",
    [
        ([2, 4, 3], [5, 6, 4], [7, 0, 8]),
        ([0], [0], [0]),
        ([9, 9, 9, 9, 9, 9, 9], [9, 9, 9, 9], [8, 9, 9, 9, 0, 0, 0, 1]),
        ([1], [9, 9, 9], [0, 0, 0, 1]),
        ([9, 9], [1], [0, 0, 1]),
    ],
)
def test_add_two_numbers(l1, l2, expected):
    from solution import Solution

    result = Solution().addTwoNumbers(list_build(l1), list_build(l2))
    assert list_to_python_list(result) == expected

Comment on your solution¶

Your solution is correct and idiomatic.

Good use of carry and divmod.
Good use of a dummy head.
The main improvement is to unify the logic into a single loop: while l1 or l2 or carry, which is shorter and avoids splitting into two loops.

## Solution
from typing import Optional

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        carry = 0
        dummy = ListNode(0)
        tail = dummy
        while l1 and l2:
            carry, digit = divmod(l1.val + l2.val + carry, 10)
            tail.next = ListNode(digit)
            tail = tail.next
            l1 = l1.next
            l2 = l2.next
        rest = l1 or l2
        while rest:
            carry, digit = divmod(rest.val + carry, 10)
            tail.next = ListNode(digit)
            tail = tail.next
            rest = rest.next
        if carry == 1:
            tail.next = ListNode(1)

        return dummy.next