Add Two Numbers
Add two non-negative integers stored as linked lists of digits, least significant digit first. A single pass with a carry, exactly like adding on paper. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
Two non-negative integers are stored as linked lists, one digit per node, with the ones digit first. For example, the number 264 is stored as 4 → 6 → 2.
Return their sum as a linked list in the same format.
Neither input has leading zeros, except the number 0 itself, which is a single node 0. Your result shouldn't have leading zeros either. In the tests, lists are written as arrays from head to tail.
Example 1
- Input
- l1 = [4, 6, 2], l2 = [8, 5]
- Output
- [2, 2, 3]
264 + 58 = 322, stored ones digit first.
Example 2
- Input
- l1 = [9, 9], l2 = [1]
- Output
- [0, 0, 1]
99 + 1 = 100. The final carry becomes a new node at the end.
Example 3
- Input
- l1 = [0], l2 = [7, 3]
- Output
- [7, 3]
Constraints
- Each list has between 1 and 100 nodes.
- 0 ≤ Node.val ≤ 9
- Neither number has leading zeros, except the number 0 itself.
Practice
Runs 11 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Add Two Numbers in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Add Two Numbers
Pattern: Digit-by-digit addition with a carry
The lists are stored ones digit first, which is the order you add numbers by hand. That's the hint: walk both lists together, add the two digits plus the carry, write sum % 10 into a new node, and carry sum // 10 into the next column.
The lists can have different lengths, so treat a missing node as the digit 0. Keep going while either list has nodes or the carry is nonzero, so a final carry like the one in 99 + 1 gets its own node. A dummy head node saves you from special-casing the first digit.
Approach 1: Convert to integers and back
Read each list into a number, add them, and write the digits of the result into a new list. It works in Python, which has arbitrary-precision integers, but a 100-digit number overflows 64-bit integers and JavaScript numbers, and it skips the point of the problem.
Time O(m + n) · Space O(m + n)
Approach 2: Single pass with a carry
- Create a
dummynode and atailpointer to it. Setcarry = 0. - While
l1,l2orcarryis non-empty: addl1.val(or 0),l2.val(or 0) andcarry. - Append a node with
total % 10, setcarry = total // 10, and advance whichever lists still have nodes. - Return
dummy.next.
The carry is never more than 1, since the largest column is 9 + 9 + 1 = 19.
Time O(max(m, n)) · Space O(max(m, n)) for the output
| Approach | Time | Space |
|---|---|---|
| Convert to integers and back | O(m + n) | O(m + n) |
| Single pass with a carry | O(max(m, n)) | O(max(m, n)) for the output |
Solution code
Try the practice editor first. Both solutions pass every test above.
Add Two Numbers solution in Python
def add_two_numbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = tail = ListNode()
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
tail.next = ListNode(total % 10)
tail = tail.next
carry = total // 10
return dummy.nextAdd Two Numbers solution in JavaScript
function addTwoNumbers(l1, l2) {
const dummy = new ListNode();
let tail = dummy;
let 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;
}
tail.next = new ListNode(total % 10);
tail = tail.next;
carry = Math.floor(total / 10);
}
return dummy.next;
}Common mistakes
- Stopping when both lists run out and dropping a final carry, so 99 + 1 comes back as [0, 0].
- Stopping as soon as the shorter list ends instead of continuing with the longer one.
- Converting to a native number in JavaScript, which loses precision past about 15 digits.
- Reading `.val` on a list that has already run out instead of treating it as 0.
What interviewers look for
Say the connection out loud: "the digits are in reverse order, so this is grade-school addition from the right." Then name the three loop conditions (either list has nodes, or there's a carry) before you write the loop, since the final-carry case is the bug interviewers watch for.
Mention why you're not converting to integers: the inputs can be 100 digits long, which overflows fixed-width types. Using a dummy head is worth calling out too, because it shows you know how to avoid edge cases rather than patch them.
Follow-up questions
What if the digits are stored most significant digit first?
Push each list onto a stack (or reverse both lists), then add from the top of the stacks and prepend each new node to the result. That keeps it O(m + n) without converting to integers.
Can you do it without allocating new nodes?
Yes. Write the sums into the nodes of the longer list as you go and only allocate one node if a final carry remains. It saves memory but destroys the inputs, so ask whether that is allowed.
How would you handle numbers in another base?
Replace 10 with the base b: write total % b and carry total // b. The carry still never exceeds 1 because the largest column is (b - 1) + (b - 1) + 1 = 2b - 1.
Companies that ask Add Two Numbers
Add Two Numbers is tagged by 125 companies in our interview dataset. The score shows how often it comes up at each company.
- General Atomics100%
- Booz Allen Hamilton100%
- Kroger100%
- Five9100%
- Earnin100%
- Ola95.8%
- Tokyo Electron93%
- Edwards Lifesciences90%
- Envato88%
- Wixcom87.3%
- Adobe86.8%
- Bloomberg85.2%
- Renesas Electronics85%
- Commscope84%
- Slalom Build83%
- Zapier83%
- Olympus82%
- Arcus Biosciences82%
- Microsoft81.4%
- Couchbase80%
- Amazon79.7%
- Google78.6%
- Boston Scientific78%
- Servicetitan77%
and 101 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required