Add Two Numbers

Two non-negative integers are stored as linked lists, one decimal digit per node, with the least significant digit first. For example, the number 382 is stored as 2 → 8 → 3.

Given the heads l1 and l2 of two such lists, return the head of a new list that stores their sum in the same reversed-digit format. Neither input has leading zeros, except the number 0 itself, which is a single node holding 0.

Lists are written as arrays in the tests, head first.

Example 1

Example 2

Example 3

Constraints

• 1 <= number of nodes in each list <= 100
• 0 <= Node.val <= 9
• Neither list has leading zeros, except the number 0 itself.

Pattern Path · Linked Lists · problem 74 of 169

Start simple

Turn each list into an integer, add them and rebuild a list: O(n) steps, but it overflows fixed-width integers for long inputs.

The key idea

Because the digits are stored ones-place first, walking both lists from the head is the same as doing column addition from right to left on paper. At every position add the two digits and the carry from the previous column; write total % 10 into a new node and carry total // 10 (always 0 or 1) into the next column.

The lists may have different lengths, so treat a list that has run out as contributing 0. The loop condition is either list remains or carry is non-zero: the final carry is what turns 99 + 1 into the three-digit 100.

A dummy head node lets every new digit be appended the same way, including the first, and the answer is dummy.next. Each node of each input is visited once, so the work is linear in the longer list, and the arithmetic never touches anything larger than 19, so there is no overflow regardless of how long the numbers are.

Complexity

• Time: O(max(m, n))
• Space: O(max(m, n)) for the output list

Python

class Solution:
    def addTwoNumbers(self, l1, l2):
        dummy = tail = ListNode(0)
        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
            carry, digit = divmod(total, 10)
            tail.next = ListNode(digit)
            tail = tail.next
        return dummy.next

JavaScript

var addTwoNumbers = function(l1, l2) {
  const dummy = new ListNode(0);
  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; }
    carry = Math.floor(total / 10);
    tail.next = new ListNode(total % 10);
    tail = tail.next;
  }
  return dummy.next;
};

What the interviewer is checking

It tests clean linked-list construction (dummy head, advancing pointers) and careful handling of unequal lengths and the final carry.

Mistakes to avoid

• Dropping the final carry, so 5 + 5 returns 0 instead of 0 → 1.
• Stopping when the shorter list ends instead of continuing with the longer one.
• Converting to integers, which overflows 64-bit types for long inputs.
• Dereferencing .next on a list that has already run out.

Follow-ups to expect

• What if digits were stored most significant first? (Use stacks or reverse first.)
• Can you write it recursively? (Pass the carry down.)
• Can you reuse the input nodes instead of allocating? (Write sums into the longer list.)

In real software

Arbitrary-precision integer libraries store numbers as sequences of digits or machine words, least significant first, and add them with exactly this carry-propagating loop.

Practice next