Add Two Numbers

Approach Summary

Traverse both lists simultaneously, summing digits and tracking carry. Append a new node for the remaining carry at the end.

Full Solution & Approach

The numbers are stored in reverse order, with the least significant digit first, which means the natural addition algorithm works from the head of both lists without any reversing. Walk both lists simultaneously, adding the two current digits plus whatever carry came from the previous column. The digit stored in the result node is total % 10, and the carry is total // 10. The important edge behavior is that the loop must continue while either list still has nodes OR the carry is non-zero — a final carry of 1 must create one extra node, as in 999 + 1 = 1000. Using a dummy head node avoids special-casing the first iteration and makes the final return trivial. Each node is visited exactly once and every operation is O(1), so the whole traversal is O(max(m, n)). This is the canonical linked-list problem that tests whether you can manage two moving pointers and a carry without losing track of any node.

We iterate over the longer of the two lists once, plus at most one extra node for a final carry — O(max(m, n)) time. Only a few pointers are allocated, so O(1) space beyond the output list.

Solution Code

Solution

def add_two_numbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0)
    cur = dummy
    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
        cur.next = ListNode(total % 10)
        cur = cur.next
        carry = total // 10
    return dummy.next

function addTwoNumbers(l1, l2) {
  const dummy = new ListNode(0);
  let cur = dummy, carry = 0;
  while (l1 || l2 || carry) {
    let total = carry;
    if (l1) { total += l1.val; l1 = l1.next; }
    if (l2) { total += l2.val; l2 = l2.next; }
    cur.next = new ListNode(total % 10);
    cur = cur.next;
    carry = Math.floor(total / 10);
  }
  return dummy.next;
}

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), cur = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
        int total = carry;
        if (l1 != null) { total += l1.val; l1 = l1.next; }
        if (l2 != null) { total += l2.val; l2 = l2.next; }
        cur.next = new ListNode(total % 10);
        cur = cur.next;
        carry = total / 10;
    }
    return dummy.next;
}

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode dummy(0), *cur = &dummy;
    int carry = 0;
    while (l1 || l2 || carry) {
        int total = carry;
        if (l1) { total += l1->val; l1 = l1->next; }
        if (l2) { total += l2->val; l2 = l2->next; }
        cur->next = new ListNode(total % 10);
        cur = cur->next;
        carry = total / 10;
    }
    return dummy.next;
}

Edge Cases to Watch

One list empty — the other list is returned via the carry-less walk
Different lengths, e.g. [9,9] + [1] — the shorter list runs out and only the carry continues
Final carry, e.g. 999 + 1 — a new head node 1 is appended
Both lists single nodes — simple two-digit sum

How to Recognize This Pattern

Digits stored in reverse order (easy carry propagation)
Handle unequal lengths by treating missing nodes as 0

Complexity Analysis

Time Complexity

O(max(m, n))

Space Complexity