2. Add Two Numbers

Problem¶

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 it 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.

Python solution¶

from typing import Optional

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        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

Comment on my 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