Introduction

When a number is stored as a linked list in forward order, the head contains the most significant digit. That makes addition awkward because elementary-school addition runs from right to left, starting at the least significant digit.

You can still add two such numbers without reversing either list. The usual solutions are recursion with padding or an explicit stack, both of which let you process digits from the tail back toward the head.

Problem Shape

Suppose the lists represent 7243 and 89:

• '7 -> 2 -> 4 -> 3'
• '8 -> 9'

The expected answer is 7332, stored as:

• '7 -> 3 -> 3 -> 2'

The constraint is that you should not reverse the input lists in place. That usually means either:

• pad the shorter list and recurse to the end
• push digits onto stacks and pop from the back

A Recursive Solution With Padding

The cleanest interview solution is to equalize the lengths first. Then you recurse until both pointers reach the tail, compute the digit sum while the call stack unwinds, and propagate carry back toward the front.

1from dataclasses import dataclass
2from typing import Optional, Tuple
3
4
5@dataclass
6class Node:
7    value: int
8    next: Optional["Node"] = None
9
10
11def length(node: Optional[Node]) -> int:
12    size = 0
13    while node:
14        size += 1
15        node = node.next
16    return size
17
18
19def pad(node: Optional[Node], count: int) -> Optional[Node]:
20    for _ in range(count):
21        node = Node(0, node)
22    return node
23
24
25def add_same_size(a: Optional[Node], b: Optional[Node]) -> Tuple[int, Optional[Node]]:
26    if a is None and b is None:
27        return 0, None
28
29    carry, tail = add_same_size(a.next, b.next)
30    total = a.value + b.value + carry
31    head = Node(total % 10, tail)
32    return total // 10, head
33
34
35def add_numbers(a: Optional[Node], b: Optional[Node]) -> Optional[Node]:
36    len_a = length(a)
37    len_b = length(b)
38
39    if len_a < len_b:
40        a = pad(a, len_b - len_a)
41    elif len_b < len_a:
42        b = pad(b, len_a - len_b)
43
44    carry, result = add_same_size(a, b)
45    if carry:
46        result = Node(carry, result)
47    return result
48
49
50def from_digits(digits):
51    head = None
52    for digit in reversed(digits):
53        head = Node(digit, head)
54    return head
55
56
57def to_list(node: Optional[Node]):
58    out = []
59    while node:
60        out.append(node.value)
61        node = node.next
62    return out
63
64
65x = from_digits([7, 2, 4, 3])
66y = from_digits([8, 9])
67print(to_list(add_numbers(x, y)))

This prints [7, 3, 3, 2].

Why Recursion Works

The recursive call moves both pointers all the way to the last digit before doing any addition. That effectively simulates “starting from the right” without mutating the lists.

Padding is important because it lines up corresponding place values. Without padding, 7 and 8 would be incorrectly treated as the same digit position in the example above.

The helper returns two pieces of information:

• the carry for the next more-significant position
• the partially built result list

That makes the algorithm easy to reason about and easy to test.

Time and Space Complexity

Let n be the length of the longer list.

• Time complexity is O(n) because each node is visited a constant number of times.
• Extra space is O(n) if you count recursion stack frames.

If recursion depth is a concern, the stack-based approach gives the same O(n) time without modifying the input lists.

A Stack-Based Alternative

The stack version is often more practical in languages where recursion depth is limited.

1
2def add_with_stacks(a: Optional[Node], b: Optional[Node]) -> Optional[Node]:
3    sa, sb = [], []
4
5    while a:
6        sa.append(a.value)
7        a = a.next
8    while b:
9        sb.append(b.value)
10        b = b.next
11
12    carry = 0
13    head = None
14
15    while sa or sb or carry:
16        total = carry
17        if sa:
18            total += sa.pop()
19        if sb:
20            total += sb.pop()
21        head = Node(total % 10, head)
22        carry = total // 10
23
24    return head

This also avoids reversing the lists. It simply moves the digits into LIFO structures first.

Common Pitfalls

A common bug is forgetting to pad the shorter list in the recursive version. That misaligns digits and gives wrong sums.

Another bug is dropping the final carry. If 999 + 1 produces 000 instead of 1000, the carry handling at the front is missing.

People also accidentally mutate the original lists while building the result. Unless the problem explicitly allows reuse, return a new list.

Finally, watch base cases carefully. Recursive list code often fails on empty input because the termination condition is too loose or too strict.

Summary

• Forward-order linked lists can be added without reversing them.
• The standard recursive solution pads the shorter list, recurses to the tail, and propagates carry backward.
• The stack-based solution is an iterative alternative with the same time complexity.
• Both approaches run in O(n) time.
• The most common mistakes are digit misalignment and forgetting the final carry node.