ASAPUtils
Invariant
The result list contains exactly the completed low-order digits, and
carryis the only information those digits pass to the next position.
Missing digits are treated as zero, which makes unequal lengths use the same loop.
Optimal solution
ListNode* addTwoNumbers(ListNode* a, ListNode* b) {
ListNode dummy;
ListNode* tail = &dummy;
int carry = 0;
while (a || b || carry) {
int x = a ? a->val : 0;
int y = b ? b->val : 0;
int sum = x + y + carry;
carry = sum / 10;
tail->next = new ListNode(sum % 10);
tail = tail->next;
if (a) a = a->next;
if (b) b = b->next;
}
return dummy.next;
}
function addTwoNumbers(a, b) {
const dummy = new ListNode();
let tail = dummy, carry = 0;
while (a || b || carry) {
const x = a?.val ?? 0;
const y = b?.val ?? 0;
const sum = x + y + carry;
carry = Math.floor(sum / 10);
tail.next = new ListNode(sum % 10);
tail = tail.next;
a = a?.next ?? null;
b = b?.next ?? null;
}
return dummy.next;
}
Why it works
For each decimal position, sum % 10 is exactly the result digit and floor(sum / 10) is exactly
the carry. Since digits are processed from least to most significant, later work cannot change an
already appended digit.
Complexity
The longer list determines the iterations: O(max(n,m)) time. The returned list contains at most max(n,m)+1 nodes. Excluding required output, auxiliary space is O(1).
Traps
- Stopping when one list ends instead of treating its missing digits as zero.
- Forgetting the final carry node.
- Using
/directly in JavaScript withoutMath.floor. - Advancing
aorbwithout checking whether it is null.
Blank re-solve prompt
Test 999 + 1 and two unequal-length inputs. State why the loop condition has three clauses before writing any node code.