Leetcode 2. Add Two Numbers

Let's understand what we're being asked to do. We have two linked lists representing numbers in reverse order. For example, the number 342 would be stored as 2 -> 4 -> 3.

If we're adding 342 + 465, the linked lists would be 2 -> 4 -> 3 and 5 -> 6 -> 4. We need to return the sum 807 as 7 -> 0 -> 8.

Let's trace through step-by-step: Start at the heads. Add 2 + 5 = 7 (first digit). Then 4 + 6 = 10 (second digit - we have a carry of 1!). Then 3 + 4 + 1 (carry) = 8 (third digit). Result: 7 -> 0 -> 8.

Important constraint: The digits are stored in reverse order, which actually makes addition easier since we naturally add from right to left (least significant digit first).

Edge cases to consider: What if the lists have different lengths? What if there's a carry at the end (like 99 + 1 = 100)? What if one or both lists are empty?

When adding numbers by hand, we start from the rightmost digit (least significant) and move left, carrying over when a sum exceeds 9.

Since the linked lists store digits in reverse order, the head of each list is already the least significant digit! This means we can traverse both lists from head to tail, adding corresponding digits and tracking the carry.

The reverse storage eliminates the need to reverse the lists or use extra space to store digits. We can build the result list as we go, adding each sum digit as a new node.

The carry mechanism is crucial: when digit1 + digit2 + carry >= 10, we store (sum % 10) in the current node and pass carry = 1 to the next addition.

Think about how you'd add 342 + 465 on paper:

  342
+ 465
-----

You'd compute: 2+5=7, then 4+6=10 (write 0, carry 1), then 3+4+1=8. Final answer: 807.

With reversed linked lists 2->4->3 and 5->6->4, we're doing the exact same process but traversing forward through the lists instead of backward through the digits!

Traverse both linked lists simultaneously from head to tail, adding corresponding digits along with any carry from the previous addition. Create a new node for each digit of the result. Handle cases where lists have different lengths by treating missing nodes as 0. After processing both lists, if there's a remaining carry, add one final node with value 1. This approach processes each digit exactly once while building the result list.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def add_two_numbers(l1, l2):
    """
    Add two numbers represented as linked lists in reverse order.
    Returns the sum as a new linked list.
    """
    # Create dummy head for result list
    dummy_head = ListNode(0)
    current = dummy_head
    carry = 0
    
    # Traverse both lists simultaneously
    while l1 is not None or l2 is not None or carry != 0:
        # Get values from current nodes (0 if node is None)
        val1 = l1.val if l1 is not None else 0
        val2 = l2.val if l2 is not None else 0
        
        # Calculate sum and new carry
        total = val1 + val2 + carry
        carry = total // 10
        digit = total % 10
        
        # Create new node with digit
        current.next = ListNode(digit)
        current = current.next
        
        # Move to next nodes if they exist
        if l1 is not None:
            l1 = l1.next
        if l2 is not None:
            l2 = l2.next
    
    # Return the result list (skip dummy head)
    return dummy_head.next

• Linked list traversal with simultaneous iteration: When processing two linked lists in parallel, use a single loop with null-safe checks (`while l1 or l2`) rather than nested loops - this elegantly handles lists of different lengths without extra complexity.
• Carry propagation pattern: In digit-by-digit arithmetic operations, maintain a carry variable that persists across iterations, adding it to each position's sum and updating it with integer division (`carry = total // 10`) - this mirrors how manual addition works column by column.
• Dummy head node technique: Create a dummy node before your result list's head to avoid special-casing the first insertion - this eliminates conditional logic for empty list initialization and simplifies returning `dummy.next` as the final result.
• Post-loop carry handling: The most common bug is forgetting to check if carry remains after both lists are exhausted - always add a final node if `carry > 0` after the main loop to handle cases like 999 + 1 = 1000.
• In-place construction optimization: Build the result list on-the-fly during traversal rather than storing values in an array first - this achieves O(1) space complexity (excluding output) and O(max(m,n)) time, processing each digit exactly once.
• Reverse-order storage insight: This problem exploits least-significant-digit-first storage which naturally aligns with how carry propagates in addition (right-to-left) - recognize that reversed representations can simplify arithmetic operations on linked lists compared to normal order.