Add Two Numbers as Linked Lists

When you add two numbers by hand, you start from the least significant digit (the rightmost one) and work left, carrying over when the sum exceeds 9. A linked list that stores digits in reverse order mirrors this process perfectly — the head is the ones digit, the next node is the tens digit, and so on. Addition becomes a simple traversal.

But what if the digits are stored in forward order? Now the head is the most significant digit, and we can’t start adding from there. This variant requires a different strategy.

We’ll solve both versions in this article.

---

Part 1: Reverse order (LeetCode 2)

Problem statement

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list (also in reverse order).

LeetCode 2 — Add Two Numbers

Example:

Input:
  l1: 2 -> 4 -> 3    (represents 342)
  l2: 5 -> 6 -> 4    (represents 465)

Output:
  7 -> 0 -> 8        (represents 807)

Because: 342 + 465 = 807

Why reverse order is convenient

When digits are stored in reverse order, the head of each list is the ones place — exactly where we start addition. We can traverse both lists left to right, adding corresponding digits and propagating the carry, building the result as we go.

  342 stored as: 2 -> 4 -> 3
  465 stored as: 5 -> 6 -> 4

  Addition (left to right on the lists):
    2 + 5 = 7,  carry = 0  =>  node 7
    4 + 6 = 10, carry = 1  =>  node 0
    3 + 4 + 1(carry) = 8   =>  node 8

  Result: 7 -> 0 -> 8  (which is 807)

Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def add_two_numbers(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)
    current = dummy
    carry = 0

    while l1 or l2 or carry:
        # Get values (0 if the list is exhausted)
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0

        # Compute sum and carry
        total = val1 + val2 + carry
        carry = total // 10
        digit = total % 10

        # Create new node
        current.next = ListNode(digit)
        current = current.next

        # Advance pointers
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next

    return dummy.next

Detailed walkthrough

l1: 2 -> 4 -> 3
l2: 5 -> 6 -> 4

carry = 0, dummy -> ...

Iteration 1:
  val1=2, val2=5, carry=0
  total = 7, carry = 0, digit = 7
  dummy -> 7
  l1=4, l2=6

Iteration 2:
  val1=4, val2=6, carry=0
  total = 10, carry = 1, digit = 0
  dummy -> 7 -> 0
  l1=3, l2=4

Iteration 3:
  val1=3, val2=4, carry=1
  total = 8, carry = 0, digit = 8
  dummy -> 7 -> 0 -> 8
  l1=None, l2=None

Loop ends (l1=None, l2=None, carry=0)

Return: 7 -> 0 -> 8

Handling different lengths

l1: 9 -> 9 -> 9 -> 9    (represents 9999)
l2: 1                    (represents 1)

Iteration 1: 9+1+0 = 10, carry=1, digit=0
Iteration 2: 9+0+1 = 10, carry=1, digit=0  (l2 exhausted, treat as 0)
Iteration 3: 9+0+1 = 10, carry=1, digit=0
Iteration 4: 9+0+1 = 10, carry=1, digit=0
Iteration 5: 0+0+1 = 1,  carry=0, digit=1  (both exhausted, but carry remains)

Result: 0 -> 0 -> 0 -> 0 -> 1  (represents 10000)

The while l1 or l2 or carry condition is crucial — it handles the case where the final carry creates an extra digit.

Complexity

Metric	Value
Time	O(max(m, n)) where m and n are the lengths of the two lists
Space	O(max(m, n)) for the result list (O(1) extra space beyond that)

---

Part 2: Forward order (LeetCode 445)

Problem statement

Given two non-empty linked lists representing two non-negative integers where the most significant digit comes first, add the two numbers and return the sum as a linked list.

LeetCode 445 — Add Two Numbers II

Example:

Input:
  l1: 7 -> 2 -> 4 -> 3    (represents 7243)
  l2: 5 -> 6 -> 4          (represents 564)

Output:
  7 -> 8 -> 0 -> 7          (represents 7807)

Because: 7243 + 564 = 7807

The challenge

With forward-order storage, the heads are the most significant digits. We can’t add them first because we don’t know the carry from less significant positions yet.

Approach 1: Use stacks

Push all digits onto stacks, then pop and add (effectively processing in reverse). This is the most straightforward approach.

def add_two_numbers_ii_stack(l1: ListNode, l2: ListNode) -> ListNode:
    # Push all digits onto stacks
    stack1, stack2 = [], []

    while l1:
        stack1.append(l1.val)
        l1 = l1.next

    while l2:
        stack2.append(l2.val)
        l2 = l2.next

    carry = 0
    head = None

    while stack1 or stack2 or carry:
        val1 = stack1.pop() if stack1 else 0
        val2 = stack2.pop() if stack2 else 0

        total = val1 + val2 + carry
        carry = total // 10
        digit = total % 10

        # Build the result list from tail to head
        new_node = ListNode(digit)
        new_node.next = head
        head = new_node

    return head

Building the list from tail to head

Notice the key difference from Part 1. Instead of appending to a dummy’s tail, we prepend each new node to the head:

new_node = ListNode(digit)
new_node.next = head
head = new_node

This builds the result in forward order without needing to reverse it at the end.

Processing (from stacks):
  3+4 = 7, carry=0  =>  head = 7
  4+6 = 10, carry=1 =>  head = 0 -> 7
  2+5+1 = 8, carry=0 => head = 8 -> 0 -> 7
  7+0 = 7, carry=0  =>  head = 7 -> 8 -> 0 -> 7

Result: 7 -> 8 -> 0 -> 7

Complexity (stack approach)

Metric	Value
Time	O(m + n)
Space	O(m + n) for the two stacks

Approach 2: Reverse both lists first

If you want to avoid stacks, reverse both input lists, apply the Part 1 algorithm, then reverse the result.

def reverse_list(head: ListNode) -> ListNode:
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev


def add_two_numbers_ii_reverse(l1: ListNode, l2: ListNode) -> ListNode:
    # Reverse both lists
    l1 = reverse_list(l1)
    l2 = reverse_list(l2)

    # Use the same algorithm as LeetCode 2
    dummy = ListNode(0)
    current = dummy
    carry = 0

    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0

        total = val1 + val2 + carry
        carry = total // 10
        digit = total % 10

        current.next = ListNode(digit)
        current = current.next

        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next

    # Reverse the result to get forward order
    return reverse_list(dummy.next)

Complexity (reverse approach)

Metric	Value
Time	O(m + n) — reverse O(m) + reverse O(n) + add O(max(m,n)) + reverse result
Space	O(max(m, n)) for the result only (O(1) extra space if we don’t count output)

This approach modifies the input lists. If that’s not allowed, use the stack approach.

---

Comparison

Approach	Problem	Time	Space	Modifies input?
Direct traversal	Reverse order (LC 2)	O(max(m,n))	O(1) extra	No
Stack-based	Forward order (LC 445)	O(m+n)	O(m+n)	No
Reverse lists	Forward order (LC 445)	O(m+n)	O(1) extra	Yes

---

Edge cases

Both lists are single nodes with large sum

l1: 5
l2: 5

5 + 5 = 10, carry = 1, digit = 0
Next iteration: carry = 1, digit = 1

Result: 0 -> 1  (reverse order) or 1 -> 0  (forward order)

One list is much longer

l1: 1 -> 0 -> 0 -> 0 -> 0    (10000)
l2: 1                          (1)

Reverse order: 0+1=1, 0+0=0, 0+0=0, 0+0=0, 1+0=1
Result: 1 -> 0 -> 0 -> 0 -> 1  (10001)

Carry cascades through the entire number

l1: 9 -> 9 -> 9    (999)
l2: 1              (1)

999 + 1 = 1000
Result (reverse): 0 -> 0 -> 0 -> 1

---

Common mistakes

1. Forgetting the final carry. If l1 = [9] and l2 = [9], the result is [8, 1] (reverse order). The loop condition must check carry too.

2. Not handling different lengths. When one list runs out, treat its values as 0. Don’t stop the loop when the shorter list ends.

3. Forward-order confusion. Students often try to add forward-order lists left to right without accounting for carry direction. This doesn’t work — you must process least-significant digits first.

4. Modifying input lists unintentionally. The reverse approach changes the original lists. If the problem forbids modification, use stacks instead.

---

Practice problems

Problem	Difficulty	Link
Add Two Numbers	Medium	LeetCode 2
Add Two Numbers II	Medium	LeetCode 445
Plus One Linked List	Medium	LeetCode 369
Multiply Strings	Medium	LeetCode 43
Add Binary	Easy	LeetCode 67

Key takeaways

• Reverse-order storage makes digit-by-digit addition natural — you process from head to tail, just like elementary school addition from right to left.
• Forward-order storage requires preprocessing: either use stacks to reverse the processing order or physically reverse the lists.
• The while l1 or l2 or carry pattern is the standard idiom for this class of problems. It handles different lengths and final carries in a single, clean loop.
• Building a result list from tail to head (prepending) is a useful technique when you need forward-order output but are processing in reverse.