AlgoMaster Logo

Add Two Numbers

mediumFrequency5 min readUpdated June 23, 2026

Understanding the Problem

We have two numbers represented as linked lists where each node holds a single digit, and the digits are stored in reverse order. So the list [2,4,3] represents the number 342. We need to add these two numbers and return the result as a linked list in the same reversed format.

The reverse storage works in our favor. Manual addition starts from the ones digit and moves left, and the lists already start at the least significant digit, so we can traverse both from head to tail and add digits in the order column-by-column addition proceeds. Nothing needs to be reversed.

The main work is handling the carry. When two digits sum to 10 or more, we carry 1 into the next position. The lists can also have different lengths, so the traversal has to continue with whichever list still has digits. Finally, after processing both lists, there might be a leftover carry that needs its own node (like 999 + 1 = 1000).

Key Constraints:

  • 1 <= list length <= 100 → Each number can have up to 100 digits. That rules out converting each list to a built-in integer, adding, and rebuilding a list: a 64-bit integer holds at most 19 digits.
  • 0 <= Node.val <= 9 → Each node holds exactly one digit. The largest column sum is 9 + 9 + 1 (incoming carry) = 19, so the carry is always 0 or 1.
  • No leading zeros → The input is well-formed. The only number with a leading zero is 0 itself (a single node with value 0).

Arbitrary-precision integers (Python's int, Java's BigInteger) would avoid the overflow, but they perform the same digit-by-digit addition with carries internally, and converting the lists to numbers and back costs an extra O(n) pass in each direction. Adding digit by digit directly on the lists is simpler and works in every language.

Approach 1: Iterative with Carry

Intuition

This mirrors column-by-column addition on paper: add the two digits in the current column, write down the ones digit, and carry into the next column. The reversed format puts the least significant digits at the heads, so one pass over both lists from head to tail performs the entire addition. At each step, the ones digit of the column sum becomes a new node in the result, and the tens digit becomes the carry for the next step.

When one list runs out before the other, treat its missing digits as 0 and keep going. Making the loop run while either list has nodes or a carry remains covers both unequal lengths and a final carry that lengthens the result, with no extra check after the loop.

A dummy head node simplifies building the result. Without one, creating the first node needs separate logic from appending later nodes. With it, every digit is appended the same way, and the answer is dummy.next.

Algorithm

  1. Create a dummy head node and a current pointer pointing to it.
  2. Initialize carry = 0.
  3. While either list still has nodes OR carry is non-zero:
    • Get the value from l1 (or 0 if l1 is exhausted).
    • Get the value from l2 (or 0 if l2 is exhausted).
    • Compute sum = val1 + val2 + carry.
    • Create a new node with value sum % 10.
    • Update carry = sum / 10 (integer division).
    • Advance l1, l2, and current to their next nodes.
  4. Return dummy.next.

Example Walkthrough

1Initialize: l1=[2,4,3], l2=[5,6,4], carry=0
2
l1
4
3
null
1/5

Code

The same digit-by-digit addition can also be written recursively, trading the explicit loop for the call stack.

Approach 2: Recursive

Intuition

Each column of the addition has the same shape: combine the two current digits with the incoming carry, produce one result node, and attach the sum of the remaining digits after it. That self-similar structure maps directly to recursion. Each call builds one node and delegates the rest of both lists, along with the outgoing carry, to the next call.

The base case is when both lists are exhausted and the carry is 0; nothing remains to add, so the call returns null. The recursion also removes the need for a dummy head: every call, including the first, returns the node it built, so the first call's return value is the head of the result.

Algorithm

  1. Define a helper function that takes l1, l2, and carry.
  2. Base case: if l1 and l2 are both null and carry is 0, return null.
  3. Compute the sum of the current values (treating an exhausted list as 0) plus carry.
  4. Create a new node with sum % 10.
  5. Set its next pointer to the recursive call on the next nodes (passing null for an exhausted list) with carry sum / 10.
  6. Return the new node.

Example Walkthrough

1Call 1: l1.val=2, l2.val=5, carry=0, sum=7 → node(7)
2
l1
4
3
null
1/5

Code