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.

Examples

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 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 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.

Thinking Process

  1. Recursive Structure: Each recursive call processes one digit from each list
  • Draw pointers before rewriting links.
  • Dummy head simplifies insert/delete at the head.
  • Slow/fast pointers find middle or detect cycles in one pass.
Linked list: pointer walk 1 2 3 slow → → fast (2x speed)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Iterative pointer walk (this problem) O(n) O(1) Traversal, insertion
Dummy head node O(n) O(1) Simplify head-edge cases
Reversal (3-pointer) O(n) O(1) Reverse sublist or full list
Slow/fast pointers O(n) O(1) Middle, cycle, merge lists

Solution

Time Complexity: O(max(m, n)) where m and n are the lengths of l1 and l2
Space Complexity: O(max(m, n)) due to recursion stack

This solution uses a recursive helper function that processes both lists simultaneously, handling carry propagation naturally through the recursion.

Solution: Recursive Helper

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def addTwoNumbers(self, l1, l2):
        return self.addTwoNumbersHelper(l1, l2, 0)

    def addTwoNumbersHelper(self, l1, l2, carry):
        # Base case: if both lists are null and no carry
        if l1 == None and l2 == None and carry == 0:
            return None

        total = carry

        if l1 != None:
            total += l1.val

        if l2 != None:
            total += l2.val

        newNode = ListNode(total % 10)

        newNode.next = self.addTwoNumbersHelper(
            l1.next if l1 != None else None,
            l2.next if l2 != None else None,
            total // 10
        )

        return newNode

Solution Explanation

Approach: Iterative pointer walk (this problem)

Key idea: 1. Recursive Structure: Each recursive call processes one digit from each list

How the code works:

  1. Recursive Structure: Each recursive call processes one digit from each list
    • Draw pointers before rewriting links.
    • Dummy head simplifies insert/delete at the head.
    • Slow/fast pointers find middle or detect cycles in one pass.

Walkthrough — input l1 = [2,4,3], l2 = [5,6,4], expected output [7,0,8]:

342 + 465 = 807.

| Approach | Time | Space | Pros | Cons | |———-|——|——-|——|——| | Recursive | O(max(m,n)) | O(max(m,n)) | Elegant, natural carry handling | Stack overflow risk, O(n) space | | Iterative (Dummy) | O(max(m,n)) | O(1) | Space efficient, clean code | Requires dummy node | | Iterative (No Dummy) | O(max(m,n)) | O(1) | Space efficient | More edge case handling |

Algorithm Breakdown

def add_two_numbers_helper(l1, l2, carry: int):
    if l1 is None and l2 is None and carry == 0:
        return None
    total = carry
    if l1 is not None:
        total += l1.val
    if l2 is not None:
        total += l2.val
    node = ListNode(total % 10)
    node.next = add_two_numbers_helper(
        l1.next if l1 is not None else None,
        l2.next if l2 is not None else None,
        total // 10,
    )
    return node

Complexity

| Approach | Time | Space | Pros | Cons | |———-|——|——-|——|——| | Recursive | O(max(m,n)) | O(max(m,n)) | Elegant, natural carry handling | Stack overflow risk, O(n) space | | Iterative (Dummy) | O(max(m,n)) | O(1) | Space efficient, clean code | Requires dummy node | | Iterative (No Dummy) | O(max(m,n)) | O(1) | Space efficient | More edge case handling |

Implementation Details

Recursive Base Case

class Solution:
    def addTwoNumbers(self, l1, l2):
        def dummy():
            return ListNode(0)

        dummy = ListNode(0)
        curr = dummy
        carry = 0

        while l1 != None or l2 != None or carry > 0:
            if l1 != None:
                carry += l1.val
                l1 = l1.next

            if l2 != None:
                carry += l2.val
                l2 = l2.next

            curr.next = ListNode(carry % 10)
            carry //= 10
            curr = curr.next

        return dummy.next

Why all three conditions?

  • l1 == nullptr && l2 == nullptr: Both lists exhausted
  • carry == 0: No remaining carry to propagate
  • If carry > 0, we need to create one more node

Digit Extraction

class Solution:
    def addTwoNumbers(self, l1, l2):
        if l1 == None:
            return l2
        if l2 == None:
            return l1

        head = None
        tail = None
        carry = 0

        while l1 != None or l2 != None or carry > 0:
            total = carry

            if l1 != None:
                total += l1.val
                l1 = l1.next

            if l2 != None:
                total += l2.val
                l2 = l2.next

            newNode = ListNode(total % 10)

            if head == None:
                head = tail = newNode
            else:
                tail.next = newNode
                tail = newNode

            carry = total // 10

        return head

Null Handling

def add_two_numbers_helper(l1, l2, carry: int):
    if l1 is None and l2 is None and carry == 0:
        return None
    # ... compute total, ListNode, recurse

When a list ends, we pass nullptr to indicate no more digits from that list.

Common Mistakes

  1. Equal length lists: [2,4,3] + [5,6,4] → [7,0,8]
  2. Different length lists: [9,9,9,9] + [9,9] → [8,9,0,0,1]
  3. Carry at end: [9,9] + [1] → [0,0,1]
  4. Single digits: [5] + [5] → [0,1]
  5. Zero inputs: [0] + [0] → [0]

  6. One list longer: [1] + [9,9,9] → [0,0,0,1]

  7. Forgetting final carry: Not handling carry after both lists end
  8. Wrong base case: Returning too early when carry > 0
  9. Null pointer dereference: Accessing l1->val when l1 is null
  10. Wrong digit calculation: Using sum / 10 instead of sum % 10 for digit
  11. Memory leaks: Not properly managing dynamically allocated nodes

Optimization Tips

  1. Iterative Preferred: For production code, use iterative approach to avoid stack overflow
  2. Dummy Node: Simplifies code by avoiding special cases for head
  3. Early Termination: Can optimize by checking if both lists are null and carry is 0
  4. In-place Modification: Could modify one list in-place to save space (not recommended)

Real-World Applications

  1. Big Integer Arithmetic: Handling numbers larger than standard data types
  2. Calculator Implementation: Adding large numbers digit by digit
  3. Cryptography: Modular arithmetic operations
  4. Financial Systems: Precise decimal calculations
  5. Scientific Computing: High-precision arithmetic

Pattern Recognition

This problem demonstrates the “Two Pointers with Carry” pattern:

Process two sequences simultaneously:
  - Handle different lengths gracefully
  - Propagate carry/borrow through iterations
  - Create result on-the-fly

Similar problems:

  • Add Binary
  • Add Strings
  • Multiply Strings
  • Plus One Linked List

Recursive vs Iterative

When to Use Recursive

  • Pros:
    • More elegant and concise
    • Natural carry propagation
    • Easier to reason about
  • Cons:
    • O(n) space for recursion stack
    • Risk of stack overflow for very long lists
    • Slightly slower due to function call overhead

When to Use Iterative

  • Pros:
    • O(1) space complexity
    • No stack overflow risk
    • Better performance
  • Cons:
    • More verbose code
    • Requires careful pointer management

Recommendation: Use iterative approach for production code, recursive for interviews/learning.

This problem is a classic introduction to linked list manipulation and demonstrates how recursion can elegantly handle carry propagation in arithmetic operations.

Key Takeaways

  1. Recursive Structure: Each recursive call processes one digit from each list
  2. Carry Propagation: Carry is passed down through recursive calls and handled at each level
  3. Unequal Length Handling: When one list ends, treat missing digits as 0
  4. Base Case: Stop when both lists are null AND carry is 0
  5. Reverse Order: Since digits are stored in reverse, we process from least significant to most significant

References

Template Reference