You are given two non-empty linked lists that represent two non-negative integers. Each node holds a single digit, and the digits are stored in reverse order — the ones digit comes first, then the tens, then the hundreds, and so on.
Add the two numbers and return their sum as a linked list, in the same reverse-order format.
You may assume neither number has a leading zero, except the number 0 itself (a single node holding 0).
carry. At each step append (sum % 10) and keep (sum / 10) — and remember a leftover carry may need its own final node.0. Keep looping while either list still has nodes, substituting 0 for whichever list has run out.[9] + [1] produces 10, so once both lists finish you may still have a carry of 1 that needs its own final node.dummy.next at the end.Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] 342 + 465 = 807, whose digits in reverse order are 7 -> 0 -> 8.
Input: l1 = [0], l2 = [0] Output: [0]
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1] 9999999 + 9999 = 10009998.
- The number of nodes in each list is in the range [1, 100]. - 0 <= Node.val <= 9 - Each list represents a number with no leading zeros (except the number 0 itself).
Adding two numbers stored as linked lists sounds fiddly, but it hides a friendly secret: it is exactly the grade-school addition you already know — the lists just happen to be pre-aligned for you.
next pointer to the following digit; the last node's next is null.10 or more, the overflow carries into the next column. That single mechanic is the whole problem.In plain terms: step through both lists together. At each step add the two current digits plus any carry, keep the last digit as a new result node, and pass the rest on as the next carry.
Worked example — l1 = [2,4,3], l2 = [5,6,4] (that is 342 + 465 = 807)
342 l1: 2 -> 4 -> 3 (read right-to-left: 3 4 2) + 465 l2: 5 -> 6 -> 4 ----- 807 result: 7 -> 0 -> 8 column 0: 2 + 5 = 7, write 7, carry 0 column 1: 4 + 6 = 10, write 0, carry 1 column 2: 3 + 4 + 1 = 8, write 8, carry 0 answer: 7 -> 0 -> 8
Confirming the shape of the input before writing a single pointer move is what separates a careful engineer from a hopeful one — most bugs here live in the ends of the lists.
“Are the two lists always non-empty?”
The constraints promise at least one node each, so you never start with a null list — but confirming it means you have thought about the empty case.
“Can the two lists have different lengths?”
Yes — 7 digits plus 4 digits is allowed, so the loop must survive one list running out before the other.
“Can the final sum have more digits than either input?”
Yes — a carry out of the most-significant column adds one extra node, like 999 + 1 becoming 1000.
“How many digits can a number have?”
Up to 100, which overflows 64-bit integers — a strong hint that converting the whole list to a number is a trap.
Before I code, let me confirm a few things about the input.
The lists store digits least-significant-first and are both non-empty — is that right?
And since a number can be up to 100 digits, I will add column by column with a carry rather than converting to an integer.
Because the digits are stored in reverse, walking both lists forward lines up matching place values automatically. No reversing, no length-counting, no aligning on the right — the hard part of paper addition is already done.
l1: 2 -> 4 -> 3 ones tens hundreds
l2: 5 -> 6 -> 4 ones tens hundreds
^ add these together, then step forward as oneAt each column the sum is d1 + d2 + carry, a value from 0 to 19. You write sum % 10 and remember sum / 10, which is always 0 or 1. One integer of state carries the entire computation.
It is tempting to stop when both lists end, but a leftover carry still needs a home. Keep looping while l1 or l2 has nodes, or the carry is non-zero — that final condition is what turns [9] + [1] into [0, 1].
| Convert to integers | Add digit by digit | |
|---|---|---|
| Idea | Rebuild both numbers, add them, split the result back into digits | Walk both lists once, summing columns with a carry |
| Time | O(m + n) | O(m + n) |
| Space | O(m + n) | O(max(m, n)) |
| Breaks when | Numbers exceed 64 bits — up to 100 digits! | Never — digits stay single-column |
The convert-to-integer idea is seductive because it feels simplest, but with up to 100 digits the numbers blow past any fixed-width integer. Adding column by column keeps every value tiny and never overflows — see the full code in the Approaches selector below.
Key takeaway
Walk both lists in lockstep, keeping a running carry. At each column append (d1 + d2 + carry) % 10 and carry the tens. Because reverse-order storage pre-aligns the digits, this single pass is all you need — and it never overflows.
dummy = new node; curr = dummy; carry = 0
while l1 or l2 or carry:
s = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
carry = s / 10
curr.next = new node(s % 10)
advance curr, and l1/l2 if present
return dummy.next