Add Two Numbers
Problem
[2,4,3] + [5,6,4]Output[7,0,8] (342+465)[9,9,9,9] + [9,9]Output[8,9,0,0,1][0] + [0]Output[0]1 ≤ nodes per list ≤ 100 · 0 ≤ Node.val ≤ 9 · no leading zeros
Try it yourself
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
}
}
sum % 10, carry sum / 10.Instinct Nodes joined by next pointers and the task is to reverse, splice, merge, reorder or remove in place - grab a dummy head and rewire pointers carefully.
Memory hack Save next, flip, step - never let go of a rope before you've grabbed the next one.
Open the Linked List Techniques guide →Approaches
Brute ForceConvert to BigInteger and Back
O((m+n)2)Space O(m+n)Read each list into a string (reversed), turn it into a number, add, then write
the digits of the result back out units-first. A long overflows at 19
digits and lists hold up to 100, so BigInteger is required — and its
decimal parse/print is quadratic in the digit count.
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { java.math.BigInteger sum = toNumber(l1).add(toNumber(l2)); String s = sum.toString(); ListNode dummy = new ListNode(0), cur = dummy; for (int i = s.length() - 1; i >= 0; i--) { cur.next = new ListNode(s.charAt(i) - '0'); cur = cur.next; } return dummy.next; } private java.math.BigInteger toNumber(ListNode node) { StringBuilder sb = new StringBuilder(); for (; node != null; node = node.next) sb.append(node.val); return new java.math.BigInteger(sb.reverse().toString()); }
Works, but leans on a big-number library and does far more work than needed.
BetterRecursion with Carry
O(max(m,n))Space O(max(m,n))Each call handles one digit position: add the two current digits (0 if a list
ran out) plus the incoming carry, create the node, and let the recursive
call build the rest with the new carry. Stops when both lists and the carry are empty.
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { return add(l1, l2, 0); } private ListNode add(ListNode a, ListNode b, int carry) { if (a == null && b == null && carry == 0) return null; int sum = carry + (a != null ? a.val : 0) + (b != null ? b.val : 0); ListNode node = new ListNode(sum % 10); node.next = add(a != null ? a.next : null, b != null ? b.next : null, sum / 10); return node; }
Clean and linear, but the call stack grows with the number of digits.
OptimalIterative Digit Addition (Dummy Head)
O(max(m,n))Space O(1) extraSame digit-by-digit addition with a loop. A dummy head removes the
“first node” special case. Looping while carry > 0 too
handles the final overflow digit (e.g. 99 + 1 = 100) without extra code.
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 sum = carry; if (l1 != null) { sum += l1.val; l1 = l1.next; } if (l2 != null) { sum += l2.val; l2 = l2.next; } carry = sum / 10; cur.next = new ListNode(sum % 10); cur = cur.next; } return dummy.next; }
Dry run[2,4,3] + [5,6,4]
- i=07c··2+5+0=7, carry 0
- i=170c·4+6+0=10 → 0, carry 1
- i=2708c3+4+1=8, carry 0 ✔
Single pass, no recursion; only the output list is allocated.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Convert to BigInteger and Back | O((m+n)2) | O(m+n) |
| Better | Recursion with Carry | O(max(m,n)) | O(max(m,n)) |
| Optimal | Iterative Digit Addition (Dummy Head) | O(max(m,n)) | O(1) extra |
- Converting to
int/long— overflows for 100-digit numbers. - Dropping the final carry —
[5]+[5]must give[0,1], not[0]. - Stopping when the shorter list ends instead of treating missing digits as 0.
- Point out the reversed order is a gift: it matches how carries propagate.
- Use a dummy head and say why: no null check for the first node.
- Clarify whether you may reuse input nodes; the safe default is a new list.