#2 Add Two Numbers

frequently reported atAdobe Bloomberg Microsoft Amazon Google Meta

the problem

In plain words

Two non-negative integers are stored as linked lists of digits in reverse order (ones digit first). Return their sum as a list in the same format.

in l1 = [2,4,3], l2 = [5,6,4]

out [7,0,8]

342 + 465 = 807.

in l1 = [0], l2 = [0]

out [0]

in l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

out [8,9,9,9,0,0,0,1]

1 ≤ nodes in each list ≤ 100
0 ≤ Node.val ≤ 9
No leading zeros except the number 0 itself

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternIn-place linked-list rewiring Simulation

where this runsJava's BigInteger.add runs this same carry loop, just over an array of 32-bit chunks instead of a list of decimal digits.

Reverse order is a gift: the lists start at the ones digit, exactly where pen-and-paper addition starts. Add digit by digit with a carry.

solutions

From brute force to optimal

Turn each list into a number, add, turn back. Needs BigInteger — 100 digits overflow long (max ≈ 9.2·10¹⁸, 19 digits).

Read digits, reverse into a string, parse BigInteger.
Add.
Write the digits back least-significant first.

timeO((n+m)²)

Adding is linear, but converting between decimal text and BigInteger's binary form is typically quadratic in the number of digits.

spaceO(n+m)

Strings and numbers of that many digits.

javajava.math.BigInteger · java.util.*

1class Solution {2    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {3        BigInteger sum = toNumber(l1).add(toNumber(l2)); // long would overflow at 100 digits4        String digits = sum.toString();5        ListNode dummy = new ListNode();6        ListNode tail = dummy;7        for (int i = digits.length() - 1; i >= 0; i--) { // least significant digit first8            tail.next = new ListNode(digits.charAt(i) - '0');9            tail = tail.next;10        }11        return dummy.next;12    }13 14    private BigInteger toNumber(ListNode head) {15        StringBuilder sb = new StringBuilder();16        for (ListNode p = head; p != null; p = p.next) sb.append(p.val);17        return new BigInteger(sb.reverse().toString()); // list stores digits in reverse18    }19}

Walk both lists together; sum = d1 + d2 + carry; write sum % 10, carry sum / 10.

dummy, tail, carry = 0.
While l1 or l2 or carry remains: add what exists.
Append sum % 10; carry = sum / 10.
Return dummy.next.

timeO(max(n, m))

One step per digit of the longer number (+1 for a final carry).

spaceO(1) extra

Apart from the output list, only a carry and pointers.

javajava.math.BigInteger · java.util.*

1class Solution {2    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {3        ListNode dummy = new ListNode();4        ListNode tail = dummy;5        int carry = 0;6        while (l1 != null || l2 != null || carry != 0) { // keep going while anything is left7            int sum = carry;8            if (l1 != null) { sum += l1.val; l1 = l1.next; }9            if (l2 != null) { sum += l2.val; l2 = l2.next; }10            tail.next = new ListNode(sum % 10);           // the digit to write11            carry = sum / 10;                             // 0 or 112            tail = tail.next;13        }14        return dummy.next;15    }16}

sim

Dry run

loading simulation…

javajava.math.BigInteger · java.util.*

1class Solution {2    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {3        ListNode dummy = new ListNode();4        ListNode tail = dummy;5        int carry = 0;6        while (l1 != null || l2 != null || carry != 0) { // keep going while anything is left7            int sum = carry;8            if (l1 != null) { sum += l1.val; l1 = l1.next; }9            if (l2 != null) { sum += l2.val; l2 = l2.next; }10            tail.next = new ListNode(sum % 10);           // the digit to write11            carry = sum / 10;                             // 0 or 112            tail = tail.next;13        }14        return dummy.next;15    }16}

in the room

How to say it in the interview

talk track

Point out why converting to long fails: up to 100 digits.
Put carry != 0 in the loop condition — it handles 5 + 5 = [0,1] without an extra if after the loop.

traps

Stopping when both lists end and dropping a final carry (5 + 5 must give [0,1]).
Advancing l1/l2 without checking for null when the lists have different lengths.

what they ask next

Follow-ups

Add Two Numbers II (LC 445) — most significant digit first?

Push digits of both lists on two stacks (or reverse both lists), add from the top, and insert each result digit at the front.

before you submit

Edge cases to test

Lists of different lengths ([1,8] + [0]).
A final carry adds a new digit (5 + 5 = [0,1]).
0 + 0 = [0].

practise next