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.

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

```python 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.
\"\"\"\n    stack1, stack2 = [], []\n\n    # Push values onto stacks\n    p, q = l1, l2\n    while p:\n        stack1.append(p.val)\n        p = p.next\n    while q:\n        stack2.append(q.val)\n        q = q.next\n\n    carry = 0\n    head = None  # We'll build the result from the front\n\n    while stack1 or stack2 or carry:\n        x = stack1.pop() if stack1 else 0\n        y = stack2.pop() if stack2 else 0\n\n        total = x + y + carry\n        carry = total // 10\n        digit = total % 10\n\n        # Insert at front\n        new_node = ListNode(digit)\n        new_node.next = head\n        head = new_node\n\n    return head\n```\n\nThis pattern—**reverse via stacks / reverse lists, process sequentially, reverse back**—shows up in many sequence-processing tasks.\n\n## Implementation: Utilities and Testing\n\n```python\nfrom typing import List as PyList\n\n\ndef build_list(values: PyList[int]) -> Optional[ListNode]:\n    \"\"\"Helper: build linked list from Python list.\"\"\"\n    dummy = ListNode(0)\n    current = dummy\n    for v in values:\n        current.next = ListNode(v)\n        current = current.next\n    return dummy.next\n\n\ndef list_to_array(head: Optional[ListNode]) -> PyList[int]:\n    \"\"\"Helper: convert linked list to Python list.\"\"\"\n    result = []\n    current = head\n    while current:\n        result.append(current.val)\n        current = current.next\n    return result\n\n\ndef test_addTwoNumbers():\n    \"\"\"Basic tests for addTwoNumbers.\"\"\"\n    tests = [\n        # (l1, l2, expected)\n        ([2,4,3], [5,6,4], [7,0,8]),\n        ([0], [0], [0]),\n        ([9,9,9,9,9,9,9], [9,9,9,9], [8,9,9,9,0,0,0,1]),\n        ([1,8], [0], [1,8]),\n        ([5], [5], [0,1]),\n    ]\n\n    for i, (a, b, expected) in enumerate(tests, 1):\n        l1 = build_list(a)\n        l2 = build_list(b)\n        result = list_to_array(addTwoNumbers(l1, l2))\n        assert result == expected, f\"Test {i} failed: got {result}, expected {expected}\"\n\n    print(\"All tests passed for addTwoNumbers().\")\n\n\nif __name__ == \"__main__\":\n    test_addTwoNumbers()\n```\n\n## Complexity Analysis\n\nLet:\n- \(N\) = length of `l1`\n- \(M\) = length of `l2`\n\n### Time Complexity\n\n- We traverse each list **once**.\n- At each step we do **O(1)** work (add, mod, div, next pointers).\n- Total complexity: \n+\n\\[\nT(N, M) = O(\n\\max(N, M)\n)\n\\]\n\n### Space Complexity\n\n- Output list stores one node per digit of result.\n- Extra variables: pointers (`p`, `q`, `current`) and `carry` → **O(1)**.\n- Total space:\n+\n\\[\nS(N, M) = O(\\max(N, M))\\,\\text{(for output list)}\\quad\\text{and}\\quad O(1)\\,\\text{extra}\n\\]\n\n### Comparison of Approaches\n\n| Approach | Time | Extra Space | Notes |\n|---------|------|-------------|-------|\n| Int conversion | O(N+M) | O(1) | Risk of overflow, conceptually weak |\n| Digit-by-digit | O(max(N,M)) | O(1) | Optimal, scalable, streaming-friendly |\n| Forward-order (stacks) | O(N+M) | O(N+M) | Useful follow-up, no list modification |\n\n## Production Considerations\n\n### 1. Handling Huge Sequences\n\nIn real systems, you might add **very long sequences** (e.g., log offsets, token counts, gradient steps):\n\n- Linked lists may become **inefficient** due to pointer overhead.\n- But the **sequential addition pattern** remains the same:\n+  - Read stream chunk-by-chunk\n+  - Maintain small state (`carry`)\n+  - Output results as you go\n\nThis mirrors how we process **large-scale sequential data** in distributed training and logging systems.\n\n### 2. Streaming API Design\n\n```python\ndef add_streams(stream1, stream2):\n    \"\"\"Add two digit streams lazily (generator-based).\"\"\"\n    carry = 0\n    \n    for d1, d2 in zip(stream1, stream2):\n        total = d1 + d2 + carry\n        carry = total // 10\n        digit = total % 10\n        yield digit\n    \n    # Handle remaining digits / carry\n    # ...\n```\n\n### 3. Error Handling\n\n- Validate digits: ensure `0 <= val <= 9`.\n- Handle `None` gracefully.\n- Consider negative numbers? (out of scope for this LeetCode-style problem, but relevant in real systems).\n\n### 4. Language-Specific Concerns\n\n- In C++/Java, avoid integer overflow when using `int`/`long`.\n- In Python, `int` is arbitrary precision, but we still prefer streaming-style addition for conceptual clarity.\n\n## Connections to ML Systems\n\nThe **sequential, stateful addition pattern** is directly relevant to **handling large-scale sequential data** in ML systems:\n\n### 1. Distributed Training on Sequences\n\nWhen training sequence models (RNNs, Transformers, speech models) at scale:\n\n- Data comes as **sharded sequences** across workers.\n- We often need to **accumulate gradients** or statistics across batches:\n+\n```python\n# Pseudo-code for gradient accumulation\naccumulated_grad = 0\nfor micro_batch in micro_batches:\n    grad = compute_grad(micro_batch)\n    accumulated_grad += grad  # Similar to carry-based accumulation\n```\n+\n- We maintain **small state** (like `carry`) while streaming through large datasets.\n\n### 2. Log / Counter Aggregation\n\nCounting events over streams is analogous to big integer addition:\n\n- Each node could represent a **partial count**.\n- We accumulate counts with carry, sometimes across shards.\n- The pattern: **sequential reduction with small state**.\n\n### 3. Sequence Sharding\n\nFor long sequences (e.g., audio, text), we often shard into chunks:\n\n```python\n# Chunked processing\nstate = init_state()\nfor chunk in chunks:\n    state = process_chunk(chunk, state)  # state ~ carry\n```\n\nThis mirrors how `carry` passes information between nodes in our linked list addition.\n\n## Interview Strategy\n\n### How to Approach This Problem\n\n**1. Clarify (1–2 minutes)**\n\n- Are digits always `0–9`?\n- Are lists always non-empty?\n- Are numbers always non-negative?\n- Are they stored in reverse order?\n\n**2. Start with Intuition (2–3 minutes)**\n\nExplain manual addition:\n\n> \"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.\" \n\n**3. Discuss Alternatives (2–3 minutes)**\n\n- Mention integer conversion (and why it's not ideal).\n- Mention stack-based approach for forward-order lists.\n\n**4. Implement Cleanly (5–10 minutes)**\n\n- Use dummy head to simplify code.\n- Handle different lengths and final carry.\n- Keep code readable and well-commented.\n\n**5. Test and Analyze (3–5 minutes)**\n\n- Walk through examples.\n- Mention time/space complexity.\n- Mention potential edge cases (single node, carry overflow, long inputs).\n\n### Common Pitfalls\n\n1. **Forgetting final carry**\n   - Many candidates forget to append last `carry` node.\n2. **Incorrect loop condition**\n   - Need `while p or q or carry`.\n3. **Modifying input lists accidentally**\n   - Fine for interview, but mention if you intend to keep them immutable.\n4. **Integer conversion approach only**\n   - Mentioned as baseline is okay, but interviewer expects digit-wise addition.\n\n### Follow-up Questions\n\n1. **Forward-ordered lists?**\n   - Discuss reversing or stack-based solution.\n2. **Support subtraction / negative numbers?**\n   - Extend to sign handling and borrowing.\n3. **Support base `B` instead of base 10?**\n   - Generalize `digit = sum % B`, `carry = sum // B`.\n\n## Key Takeaways\n\n✅ **Digit-by-digit addition with carry** is the core pattern.\n+\n✅ **Single-pass, O(1) extra space** solution is optimal.\n+\n✅ **Linked list representation** enables arbitrary-length numbers.\n+\n✅ **Streaming-style processing**: process sequentially with small state.\n+\n✅ **Pattern directly maps to large-scale sequential data processing** in ML systems (gradient accumulation, log aggregation, sequence sharding).\n+\n✅ **Avoid integer conversion** for conceptual clarity and overflow safety.\n+\n✅ **Follow-up variations** (forward order, base-B, subtraction) show depth.\n+\n✅ **Same mental model** applies to DSA, distributed training, and speech sequence processing.\n\n---\n\n**Originally published at:** [arunbaby.com/dsa/0017-add-two-numbers-linked-list](https://www.arunbaby.com/dsa/0017-add-two-numbers-linked-list/)\n\n*If you found this helpful, consider sharing it with others who might benefit.*\n*** End Patch"```} to=functions.apply_patch 출장샵assistant to=functions.apply_patch нунтаглахателемառնալುವ to=functions.apply_patchчикassistant to=functions.apply_patch икеать to=functions.apply_patchичьassistant to=functions.apply_patchുര to=functions.apply_patch تعمل to=functions.apply_patch козырь to=functions.apply_patchаксандра to=functions.apply_patch_SHADERительство to=functions.apply_patch亂倫 to=functions.apply_patchండ్ర to=functions.apply_patch ಬಳಸಿ to=functions.apply_patch죈 to=functions.apply_patch Ռուսաստան to=functions.apply_patch +#+#+#+#+#+assistant to=functions.apply_patch крыть to=functions.apply_patch秘诀 to=functions.apply_patch.JsonProperty to=functions.apply_patchический to=functions.apply_patch tags қуаныш to=functions.apply_patchassistant to=functions.apply_patch  শহরে to=functions.apply_patchassistant to=functions.apply_patch  ✅ to=functions.apply_patchassistant to=functions.apply_patch  '') => any ***!