Add Two Numbers

Intuition

This is grade-school addition expressed on linked lists. Because the digits are already stored least-significant-first, we can add left to right exactly the way we add columns of numbers by hand. At each step we combine the current digit from each list plus any carry from the previous column. The units digit of that sum becomes a new node, and anything that overflows past nine becomes the carry into the next column. A dummy head lets us append nodes without special-casing the very first one, and we keep going until both lists are exhausted and no carry remains.

Algorithm walkthrough

1. 1Create a dummy node and a tail pointer that starts at the dummy; initialize carry to 0.
2. 2Loop while either list still has nodes or the carry is non-zero.
3. 3Read the current value from each list (treating a missing node as 0), then compute sum = digit1 + digit2 + carry.
4. 4Append a new node holding sum % 10 to the tail, and set carry = sum / 10 (integer division).
5. 5Advance the tail and advance each list pointer that still has a node.
6. 6After the loop, return dummy.next, which is the head of the summed list.

Implementation

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        tail = dummy
        carry = 0
        while l1 or l2 or carry:
            digit1 = l1.val if l1 else 0
            digit2 = l2.val if l2 else 0
            total = digit1 + digit2 + carry
            carry = total // 10
            tail.next = ListNode(total % 10)
            tail = tail.next
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
        return dummy.next