Approach Summary
Traverse both lists simultaneously, summing digits and tracking carry. Append a new node for the remaining carry at the end.
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
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
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;
}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.nextfunction 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;
}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
Master the Linked List Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Linked List pattern.
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
O(max(m, n))