Algorithm: Add Two Numbers from LeetCode

Quiz

Can you make this code faster?

from typing import Optional


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


class Solution:
    def addTwoNumbers(
        self, l1: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        if l1 is None and l2 is None:
            return None

        def build_number_from(l: ListNode) -> int:
            if l is None:
                return 0
            stack = []
            current = l
            while current:
                stack.append(current.val)
                current = current.next
            number = 0
            while len(stack) > 0:
                place = len(stack) - 1
                digit = stack.pop()
                number += digit * 10 ** (place)
            return number

        number_l1 = build_number_from(l1)
        number_l2 = build_number_from(l2)
        result = number_l1 + number_l2

        def build_linked_list_from(number: int) -> ListNode:
            number_str = str(number)
            idx = 0
            head = None
            while idx < len(number_str):
                item = int(number_str[idx])
                if head:
                    new_head = ListNode(item)
                    new_head.next = head
                    head = new_head
                else:
                    head = ListNode(item)
                idx += 1
            return head

        return build_linked_list_from(result)

At first glance, this solution looks reasonable and easy to understand. But it is slower than necessary.

Answer

Computing Complexity Analysis

Let n be the number of nodes in l1, and let m be the number of nodes in l2.

Time complexity

• Traversing the linked list: O(n + m)
• Rebuilding the numbers using 10 ** place: O(n + m)
• Converting the result to a string: O(n + m)

So overall time complexity is O(n + m).

👉 But: constant factors matter.

Space complexity

• Stack to store digits: O(n + m)
• Python big integers for the full numbers: O(n + m)
• String conversion of the result: O(n + m)

What’s the Real Problem?

Even though the asymptotic complexity looks fine, the implementation is inefficient because:

1. Big integer construction

   • Python integers grow dynamically.
   • Repeated exponentiation (10 ** place) is expensive.

2. Unnecessary conversions

   • Linked list → integer → string → linked list
   • Multiple representations of the same data.

3. Doesn’t match the problem structure

   • The problem is digit-by-digit addition.
   • But the solution treats it as a large arithmetic problem.

Optimized Solution

Instead, we can:

• Traverse both lists once
• Add digits directly with a carry
• Build the result list as we go

New Solution

from typing import Optional


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


class Solution:
    def addTwoNumbers(
        self, l1: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        dummy = ListNode(0)
        tail = dummy
        carry = 0

        while l1 or l2 or carry:
            a = l1.val if l1 else 0
            b = l2.val if l2 else 0

            total = a + b + carry
            carry = total // 10
            digit = total % 10

            tail.next = ListNode(digit)
            tail = tail.next

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

        return dummy.next

• Time complexity: O(n + m)
• No extra space: O(1) (excluding the output list)
• No big integers
• No string conversion
• No exponentiation