Add Two Numbers

MediumLinked List

Two non-empty linked lists store digits in reverse order. Add the numbers and return the sum as a linked list.

Constraints

1 <= each list length <= 100
0 <= Node.val <= 9

Digit-by-digit with carry

Time O(max(n, m))Space O(max(n, m))

Walk both lists together adding corresponding digits plus a carry, creating a new node for each resulting digit. Continue while either list remains or a carry is left.

struct ListNode { int val; ListNode* next; };

ListNode* addTwoNumbers(ListNode* a, ListNode* b) {
    ListNode dummy(0), *tail = &dummy;
    int carry = 0;
    while (a || b || carry) {
        int sum = carry;
        if (a) { sum += a->val; a = a->next; }
        if (b) { sum += b->val; b = b->next; }
        carry = sum / 10;
        tail->next = new ListNode{sum % 10, nullptr};
        tail = tail->next;
    }
    return dummy.next;
}