Add Two Numbers (Linked List)

Simulate arbitrary-precision addition on linked lists, the same sequential pattern used in large-scale distributed training and streaming pipelines.

TL;DR

Walk both linked lists simultaneously, adding digits with a carry variable, exactly like grade-school addition. Use a dummy head node to simplify list construction and handle the final carry. Runs in O(max(N,M)) time with O(1) extra space. This sequential stateful processing pattern is the foundation of streaming pipelines and gradient accumulation. For more linked list patterns, see Reverse Linked List and Merge Sorted Lists.

Problem Statement

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

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Each linked list node is defined as:

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

Examples

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]

Explanation:
342 + 465 = 807

Lists (reverse order):
 l1: 2 -> 4 -> 3 (342)
 l2: 5 -> 6 -> 4 (465)
 sum: 7 -> 0 -> 8 (807)

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9]
 l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Explanation:
9999999 + 9999 = 10009998

Constraints

• The number of nodes in each linked list is in the range ([1, 100]).
• (0 \le \text{Node.val} \le 9)
• It is guaranteed that the list represents a number without leading zeros.

Understanding the Problem

This problem is big integer addition implemented on a linked list representation:

• Number is stored least-significant digit first (reverse order)
• Each node stores a digit ([0, 9])
• We must add digit-by-digit and propagate carry, like manual addition

Why Linked Lists?

1. Numbers can be arbitrarily long (beyond 64-bit integer limits).
2. We can add numbers without converting full lists to integers.
3. Sequential, node-by-node processing mirrors streaming and large-scale sequence processing:
   • You don’t always have the whole sequence in memory.
   • You process a stream element-by-element and maintain a small state (carry).

Key Observations

• Addition proceeds from least significant digit to most, which matches the list order.
• At each step:
• Sum current digits + carry.
• New digit = sum % 10
• New carry = sum // 10
• If one list is shorter, treat missing digits as 0.
• After processing all nodes, if carry > 0, append final node.

This is a single-pass, linear-time algorithm with constant extra space (excluding output list).

Approach 1: Convert to Integers (Brute Force, Not Robust)

Intuition

1. Traverse l1 to build integer n1.
2. Traverse l2 to build integer n2.
3. Compute n3 = n1 + n2.
4. Convert n3 back to linked list.

Implementation

from typing import Optional

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


    def list_to_int(l: Optional[ListNode]) -> int:
        \"\"\"Convert reverse-order linked list to integer.\"\"\"
        num = 0
        multiplier = 1
        current = l
        while current:
            num += current.val * multiplier
            multiplier *= 10
            current = current.next
            return num


    def int_to_list(n: int) -> Optional[ListNode]:
        \"\"\"Convert integer to reverse-order linked list.\"\"\"
        if n == 0:
            return ListNode(0)

            dummy = ListNode(0)
            current = dummy

            while n > 0:
                digit = n % 10
                current.next = ListNode(digit)
                current = current.next
                n //= 10

                return dummy.next


    def addTwoNumbers_bruteforce(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        \"\"\"Brute force: convert lists to ints, add, convert back.

        Time: O(N + M) to traverse + log(result) to rebuild
        Space: O(1) extra (excluding result)

        Problems:
            - Breaks for very large numbers (beyond Python's int in other languages).
            - Violates the spirit of the problem (expectation: digit-by-digit).
            \"\"\"
            n1 = list_to_int(l1)
            n2 = list_to_int(l2)
            return int_to_list(n1 + n2)

Why This Is Not Ideal

1. Overflow risk in languages with fixed-size integers.
2. Doesn’t scale conceptually to arbitrarily long sequences.
3. Interview red flag: Interviewer expects digit-wise addition.

We need a streaming-style, node-by-node addition.

Approach 2: Digit-by-Digit Addition (Optimal)

Intuition

Simulate exactly how you add two numbers by hand:

1. Start with carry = 0.
2. Walk both lists simultaneously:
   • x = l1.val if l1 else 0
   • y = l2.val if l2 else 0
   • sum = x + y + carry
   • digit = sum % 10
   • carry = sum // 10
3. Append digit as new node to result list.
4. Move l1 = l1.next, l2 = l2.next.
5. After loop, if carry > 0, append final node.

This is a single pass over the lists with constant state (only carry).

Implementation

from typing import Optional

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


    def addTwoNumbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        \"\"\"Add two numbers represented by linked lists (reverse order).

        Time: O(max(N, M))
        Space: O(max(N, M)) for result list, O(1) extra

        This is the production-ready solution:
            - Single pass
            - Constant extra space
            - No overflow
            \"\"\"
            # Dummy head simplifies list construction
            dummy_head = ListNode(0)
            current = dummy_head
            carry = 0

            p = l1
            q = l2

            while p is not None or q is not None or carry != 0:
                # Extract values (0 if list is shorter)
                x = p.val if p is not None else 0
                y = q.val if q is not None else 0

                # Digit-wise addition + carry
                total = x + y + carry
                carry = total // 10
                digit = total % 10

                # Append new node with digit
                current.next = ListNode(digit)
                current = current.next

                # Advance pointers
                if p is not None:
                    p = p.next
                    if q is not None:
                        q = q.next

                        # dummy_head.next is the actual head
                        return dummy_head.next

Walkthrough Example

Example: l1 = [2,4,3], l2 = [5,6,4]

Step 1:
 x = 2, y = 5, carry = 0
 total = 7 → digit = 7, carry = 0
 result: 7

Step 2:
 x = 4, y = 6, carry = 0
 total = 10 → digit = 0, carry = 1
 result: 7 -> 0

Step 3:
 x = 3, y = 4, carry = 1
 total = 8 → digit = 8, carry = 0
 result: 7 -> 0 -> 8

Done (no more nodes, carry = 0)
Output: [7,0,8]

Handling Different Lengths

Example: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

We keep treating missing digits as 0:

 9999999
+ 9999
---------
 10009998

Lists (reverse):
 l1: 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9
 l2: 9 -> 9 -> 9 -> 9

Processing:
 Step 1: 9+9=18 → 8, carry=1
 Step 2: 9+9+1=19 → 9, carry=1
 Step 3: 9+9+1=19 → 9, carry=1
 Step 4: 9+9+1=19 → 9, carry=1
 Step 5: 9+0+1=10 → 0, carry=1
 Step 6: 9+0+1=10 → 0, carry=1
 Step 7: 9+0+1=10 → 0, carry=1
 Step 8: 0+0+1=1 → 1, carry=0

Result: 8 -> 9 -> 9 -> 9 -> 0 -> 0 -> 0 -> 1 (10009998)

Approach 3: Forward-Order Lists (Follow-up)

Sometimes the number is stored most significant digit first:

Input:
 l1 = [7,2,4,3] (7243)
 l2 = [5,6,4] (564)

Output:
 [7,8,0,7] (7243 + 564 = 7807)

Here we can:

1. Reverse both lists, use our addTwoNumbers, then reverse result.
2. Or use stacks to simulate reverse traversal without modifying lists.

Stack-Based Implementation

def addTwoNumbers_forward(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    """Add two numbers where digits are stored in forward order.

    Uses stacks to simulate reverse traversal.
    """
    stack1, stack2 = [], []

    # Push values onto stacks
    p, q = l1, l2
    while p:
        stack1.append(p.val)
        p = p.next
    while q:
        stack2.append(q.val)
        q = q.next

    carry = 0
    head = None  # We'll build the result from the front

    while stack1 or stack2 or carry:
        x = stack1.pop() if stack1 else 0
        y = stack2.pop() if stack2 else 0

        total = x + y + carry
        carry = total // 10
        digit = total % 10

        # Insert at front
        new_node = ListNode(digit)
        new_node.next = head
        head = new_node

    return head

This pattern, reverse via stacks / reverse lists, process sequentially, reverse back, shows up in many sequence-processing tasks.

Implementation: Utilities and Testing

from typing import List as PyList


def build_list(values: PyList[int]) -> Optional[ListNode]:
    """Helper: build linked list from Python list."""
    dummy = ListNode(0)
    current = dummy
    for v in values:
        current.next = ListNode(v)
        current = current.next
    return dummy.next


def list_to_array(head: Optional[ListNode]) -> PyList[int]:
    """Helper: convert linked list to Python list."""
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result


def test_addTwoNumbers():
    """Basic tests for addTwoNumbers."""
    tests = [
        # (l1, l2, expected)
        ([2,4,3], [5,6,4], [7,0,8]),
        ([0], [0], [0]),
        ([9,9,9,9,9,9,9], [9,9,9,9], [8,9,9,9,0,0,0,1]),
        ([1,8], [0], [1,8]),
        ([5], [5], [0,1]),
    ]

    for i, (a, b, expected) in enumerate(tests, 1):
        l1 = build_list(a)
        l2 = build_list(b)
        result = list_to_array(addTwoNumbers(l1, l2))
        assert result == expected, f"Test {i} failed: got {result}, expected {expected}"

    print("All tests passed for addTwoNumbers().")


if __name__ == "__main__":
    test_addTwoNumbers()

Complexity Analysis

Let:

• \(N\) = length of l1
• \(M\) = length of l2

Time Complexity

• We traverse each list once.
• At each step we do O(1) work (add, mod, div, next pointers).
• Total complexity:

\[ T(N, M) = O(\max(N, M)) \]

Space Complexity

• Output list stores one node per digit of result.
• Extra variables: pointers (p, q, current) and carry – O(1).
• Total space:

\[ S(N, M) = O(\max(N, M))\,\text{(for output list)}\quad\text{and}\quad O(1)\,\text{extra} \]

Comparison of Approaches

Approach	Time	Extra Space	Notes
Int conversion	O(N+M)	O(1)	Risk of overflow, conceptually weak
Digit-by-digit	O(max(N,M))	O(1)	Optimal, scalable, streaming-friendly
Forward-order (stacks)	O(N+M)	O(N+M)	Useful follow-up, no list modification

Production Considerations

1. Handling Huge Sequences

In real systems, you might add very long sequences (e.g., log offsets, token counts, gradient steps):

• Linked lists may become inefficient due to pointer overhead.
• But the sequential addition pattern remains the same:
  • Read stream chunk-by-chunk
  • Maintain small state (carry)
  • Output results as you go

This mirrors how we process large-scale sequential data in distributed training and logging systems.

2. Streaming API Design

def add_streams(stream1, stream2):
    """Add two digit streams lazily (generator-based)."""
    carry = 0

    for d1, d2 in zip(stream1, stream2):
        total = d1 + d2 + carry
        carry = total // 10
        digit = total % 10
        yield digit

    # Handle remaining digits / carry
    # ...

3. Error Handling

• Validate digits: ensure 0 <= val <= 9.
• Handle None gracefully.
• Consider negative numbers? (out of scope for this LeetCode-style problem, but relevant in real systems).

4. Language-Specific Concerns

• In C++/Java, avoid integer overflow when using int/long.
• In Python, int is arbitrary precision, but we still prefer streaming-style addition for conceptual clarity.

Connections to ML Systems

The sequential, stateful addition pattern is directly relevant to handling large-scale sequential data in ML systems:

1. Distributed Training on Sequences

When training sequence models (RNNs, Transformers, speech models) at scale:

• Data comes as sharded sequences across workers.
• We often need to accumulate gradients or statistics across batches:

# Pseudo-code for gradient accumulation
accumulated_grad = 0
for micro_batch in micro_batches:
    grad = compute_grad(micro_batch)
    accumulated_grad += grad  # Similar to carry-based accumulation

• We maintain small state (like carry) while streaming through large datasets.

2. Log / Counter Aggregation

Counting events over streams is analogous to big integer addition:

• Each node could represent a partial count.
• We accumulate counts with carry, sometimes across shards.
• The pattern: sequential reduction with small state.

3. Sequence Sharding

For long sequences (e.g., audio, text), we often shard into chunks:

# Chunked processing
state = init_state()
for chunk in chunks:
    state = process_chunk(chunk, state)  # state ~ carry

This mirrors how carry passes information between nodes in our linked list addition.

Interview Strategy

How to Approach This Problem

1. Clarify (1-2 minutes)

• Are digits always 0-9?
• Are lists always non-empty?
• Are numbers always non-negative?
• Are they stored in reverse order?

2. Start with Intuition (2-3 minutes)

Explain manual addition:

“I’ll simulate grade-school addition: add digits from least to most significant with a carry. Since lists are in reverse order, I can walk them from head to tail, adding node-by-node and maintaining a carry.”

3. Discuss Alternatives (2-3 minutes)

• Mention integer conversion (and why it’s not ideal).
• Mention stack-based approach for forward-order lists.

4. Implement Cleanly (5-10 minutes)

• Use dummy head to simplify code.
• Handle different lengths and final carry.
• Keep code readable and well-commented.

5. Test and Analyze (3-5 minutes)

• Walk through examples.
• Mention time/space complexity.
• Mention potential edge cases (single node, carry overflow, long inputs).

Common Pitfalls

1. Forgetting final carry
   • Many candidates forget to append last carry node.
2. Incorrect loop condition
   • Need while p or q or carry.
3. Modifying input lists accidentally
   • Fine for interview, but mention if you intend to keep them immutable.
4. Integer conversion approach only
   • Mentioned as baseline is okay, but interviewer expects digit-wise addition.

Follow-up Questions

1. Forward-ordered lists?
   • Discuss reversing or stack-based solution.
2. Support subtraction / negative numbers?
   • Extend to sign handling and borrowing.
3. Support base B instead of base 10?
   • Generalize digit = sum % B, carry = sum // B.

Key Takeaways

• Digit-by-digit addition with carry is the core pattern.
• Single-pass, O(1) extra space solution is optimal.
• Linked list representation enables arbitrary-length numbers.
• Streaming-style processing: process sequentially with small state.
• Pattern directly maps to large-scale sequential data processing in ML systems (gradient accumulation, log aggregation, sequence sharding).
• Avoid integer conversion for conceptual clarity and overflow safety.
• Follow-up variations (forward order, base-B, subtraction) show depth.
• Same mental model applies to DSA, distributed training, and speech sequence processing.

FAQ

How do you add two numbers represented as linked lists?

Traverse both lists from head to tail, adding corresponding digits plus a carry value. Create new nodes for each result digit using a dummy head to simplify construction. Handle different-length lists by treating missing nodes as zero. The critical detail is the final carry: after both lists are exhausted, if carry is non-zero, append one more node. This digit-by-digit approach runs in O(max(N,M)) time with O(1) extra space.

Why are the digits stored in reverse order?

Reverse order aligns the least significant digits at the head of each list, allowing addition to proceed naturally from least to most significant digit, exactly like manual addition. This eliminates the need to know list lengths in advance or reverse the lists before processing. The forward-order variant requires stacks or list reversal as a preprocessing step.

What if the two linked lists have different lengths?

The algorithm handles this naturally with the loop condition while p or q or carry. When one list is exhausted, treat its missing digits as zero and continue adding with the remaining list and any carry until both lists and the carry are fully processed. No padding or length equalization is needed.

How do you handle the forward-order variant of this problem?

Use stacks to reverse the traversal order without modifying the original lists. Push all digits onto separate stacks, then pop and add with carry, building the result list from the head by inserting each new node at the front. Alternatively, reverse both lists first, apply the standard algorithm, and reverse the result. Both approaches run in O(N+M) time with O(N+M) extra space for the stacks.

---

Originally published at: arunbaby.com/dsa/0017-add-two-numbers-linked-list