Add Two Numbers

Given two non-empty linked lists representing non-negative integers in reverse order — each node holds one digit — add them and return the sum as the same reversed representation. The machine must simulate grade-school column addition, digit by digit, carrying overflow forward.

The key insight: reverse order means the least-significant digit is at the head, so a single forward pass with a running carry produces the answer in the correct orientation with no reversing. You cannot convert to an integer — real inputs exceed 64-bit range — so the whole sum happens one node at a time.

Approach:

1. Walk both lists with a carry accumulator, adding aligned digits plus carry.
2. Append digit % 10 as a new node and keep carry = digit // 10.
3. After both lists exhaust, append one final node if carry is still 1.

def add_two_numbers(l1, l2):
    dummy = tail = ListNode(0)
    carry = 0
    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

Time: O(max(n, m)). Space: O(max(n, m)) for the result list.

Trickiest edge case: the final carry — 9 + 9 must produce a new node with digit 1, which is why the loop condition includes or carry.