AlgoMaster Logo

Add Two Numbers II

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We have two linked lists where the digits are stored in forward order, meaning the head is the most significant digit. We need to add the two numbers they represent and return the result as a linked list, also in forward order.

Addition works from right to left, starting at the least significant digit, but the lists give us digits from the left, most significant first. We need a way to process digits starting from the end of each list.

The follow-up constraint (no reversing) pushes us toward stack-based or recursive approaches, both of which provide last-in, first-out access to the digits.

Key Constraints:

  • Number of nodes in range [1, 100] → Lists are short, so time limits do not constrain the choice of approach. All approaches below run in O(n + m) anyway, since every digit has to be read at least once.
  • 0 <= Node.val <= 9 → Each node holds a single digit, so the carry at any position is 0 or 1 (the largest possible column sum is 9 + 9 + 1 = 19).
  • No leading zeros → The result never needs leading zeros stripped. It has either the same number of digits as the longer input or one more, when a final carry remains (999 + 1 = 1000).

Approach 1: Reverse Lists Then Add

Intuition

Reverse both lists so the least significant digit comes first, perform the standard digit-by-digit addition with carry, then reverse the result to restore most-significant-first order.

This is easy to implement correctly, but it modifies the input lists (unless you copy them first), and the follow-up asks for a solution that leaves the inputs untouched.

Algorithm

  1. Reverse both input lists l1 and l2.
  2. Initialize a carry variable to 0 and a dummy head for the result list.
  3. Traverse both reversed lists simultaneously. At each step, compute sum = digit1 + digit2 + carry.
  4. Create a new node with value sum % 10 and update carry = sum / 10.
  5. After both lists are exhausted, if carry is still 1, add one more node.
  6. Reverse the result list to restore most-significant-first order.

Visualization and Code

Loading animation...

The next approach reads the digits in reverse order without touching the list structure, so the inputs survive intact and the three reverse passes disappear.

Approach 2: Using Stacks

Intuition

A stack gives last-in, first-out access. Push every digit from both lists onto its own stack, and the least significant digits sit on top, ready to be added first. The lists themselves are only read, never modified, which answers the follow-up.

The result is built without a final reverse. We compute digits from least significant to most significant, so appending them to a list would produce them in reverse order. Instead, we prepend each new node to the front. Computing digits 7, 0, 8, 7 from right to left: create node 7, prepend 0 to get 0->7, prepend 8 to get 8->0->7, prepend 7 to get 7->8->0->7. Each digit is more significant than everything already in the list, so placing it at the head keeps the list in correct order at every step.

A variant pushes each computed digit onto a third stack and pops that stack into a forward-order list at the end. It produces the same answer with one extra stack and one extra pass. Prepending does the same job in a single pass, so that is what the code below uses.

Algorithm

  1. Push all values from l1 onto stack s1 and all values from l2 onto stack s2.
  2. Initialize carry = 0 and head = null.
  3. While either stack is non-empty or carry is non-zero:
    • Pop from s1 if non-empty, otherwise use 0. Same for s2.
    • Compute sum = val1 + val2 + carry.
    • Create a new node with value sum % 10.
    • Point this new node's next to the current head, then update head to this new node.
    • Update carry = sum / 10.
  4. Return head.

Visualization and Code

Loading animation...

The stacks store every digit from both lists, O(n + m) extra memory on top of the result. Recursion can replace them: recurse to the end of both lists and add digits as the calls return, with the call stack holding the positions instead. That cuts the auxiliary space to O(max(n, m)) of recursion depth.

Approach 3: Recursive with Padding

Intuition

A function that recurses before processing its node reaches the deepest node first, so the least significant digits get added first and the more significant ones are handled as the calls return. The complication is that the two lists might have different lengths. If l1 has 4 digits and l2 has 3, the ones digits, tens digits, hundreds digits, and so on must line up.

To align them, compute the length of each list and treat the shorter one as if it were padded with leading zeros. Instead of adding zero nodes, the recursion advances only the longer list for the first len1 - len2 steps, pairing those extra digits with an implicit 0; after that, both lists advance together.

The carry from a deeper call must propagate upward, so the recursive function returns the carry alongside the node it builds. Each call reads the carry produced by the call below it, adds its own digits, and passes its own carry up. If a carry remains after the topmost call, the result gains one extra leading node with value 1.

Algorithm

  1. Compute the lengths of both lists. Swap them if needed so l1 is the longer (or equal) one.
  2. Call the recursive helper with diff = len1 - len2. While diff > 0, recurse on l1.next only, pairing l1.val with an implicit 0 and decrementing diff.
  3. Once diff reaches 0, recurse on l1.next and l2.next together.
  4. At the base case (l1 is null), return carry = 0.
  5. As each call returns, compute sum = digit(s) + carry_from_deeper, create a node with sum % 10, link it in front of the deeper result, and pass sum / 10 up as the carry.
  6. If a carry of 1 remains after the topmost call, prepend a node with value 1.

Visualization and Code

Loading animation...