LeetCode 2: Add Two Numbers Solution in Python

Adding two numbers represented by singly linked lists can be a challenging task when the numbers are stored in reverse order. This is precisely what LeetCode’s Add Two Numbers problem covers, as a challenge to programmers. This article explores a Python solution that traverses the lists, extracts and sums the numerical values, and constructs a new list that represents the sum. The time and space complexity of the algorithm are also analyzed.

# 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: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        multiplier = 1
        l1_temp = l1
        l2_temp = l2
        l1_num = l2_num = 0
        while l1_temp != None:
            l1_num += l1_temp.val * multiplier
            multiplier *= 10
            l1_temp = l1_temp.next

        # Reset for the second linked list
        multiplier = 1  

        while l2_temp != None:
            l2_num += l2_temp.val * multiplier
            multiplier *= 10
            l2_temp = l2_temp.next

        # Normal integer addition
        result = l1_num + l2_num

        # Save last digit first
        l3 = ListNode(result % 10)  
        l3_temp = l3

        while result > 0:
            result //= 10
            if result > 0:
                # Create a node with the value
                l3_temp.next = ListNode(result % 10)
            # Move the pointer
            l3_temp = l3_temp.next  

        return l3

Understanding the Add Two Numbers Python Solution Logic

The code snippet provided outlines a method within a Solution class designed to add two numbers that are represented as two singly-linked lists, where each node contains a single digit, and the digits are stored in reverse order. At the core of this implementation is the addTwoNumbers method, which accepts two arguments, l1 and l2. These arguments are references to the heads of the singly-linked lists representing the numbers to be added. The method’s objective is to return a new singly-linked list that represents the sum of the input numbers, also in reverse order.

The process begins by initializing variables to iterate through the lists (l1_temp, l2_temp) and to accumulate the numerical values of these lists (l1_num, l2_num). The accumulation is done by traversing each list individually, converting the list-based numerical representation into an actual integer value. This conversion uses a multiplier that starts at 1 (for the unit place) and increases tenfold with each step (moving to tens, hundreds, etc.), effectively placing each digit at its correct value in the integer representation.

Once both numbers are fully extracted from their list representations, they are added together to produce a single integer result. This result is then used to construct a new singly-linked list (l3) that represents the sum. The construction starts with the least significant digit (the result of result % 10) and proceeds by dividing the result by 10 to access the next digit. A new node for each digit is created and appended to the list until all digits have been processed.

This implementation allows for the addition of numbers that could potentially exceed the language’s integer limits by operating on their digit-by-digit representation in a linked list format. The final output is the head of a newly formed list that encapsulates the sum of the two input numbers, adhering to the specified reverse order digit representation.

Add Two Numbers Time Complexity

The analysis of the time and space complexity for my Python solution, which adds two numbers represented by singly-linked lists, without explicit carry logic during addition, is as follows:

List Traversal and Integer Conversion: The algorithm iterates through each of the two input lists (l1 and l2) a single time to convert their list-based numerical representation into integer values. This process has a time complexity of O(n) and O(m), respectively, where n and m are the lengths of l1 and l2. This step is linear with respect to the size of the input lists.

Result List Construction: After computing the sum as an integer, the algorithm constructs the resultant list. The time complexity for constructing this list is proportional to the number of digits in the sum, O(k). However, since the sum’s digit count is less directly tied to the input lists’ lengths and more to their numerical values, k can be considered in terms of n and m for simplicity in analysis. The construction step’s complexity is also linear with respect to the number of digits in the sum.

Given the separate traversal and conversion of the two lists, followed by the construction of the result list, the overall time complexity can be considered O(n+m), reflecting the sequential handling of each list and the sum’s digit count. This notation captures the linear relationship between the algorithm’s runtime and the lengths of the input lists.

Add Two Numbers Space Complexity

Temporary Variables: The space utilized by temporary variables for calculations and iterations (including the integer representations of the list values and the pointers for list traversal) is constant, O(1). These variables do not scale with the input size.

The overall space complexity of the solution is O(max(n,m)+1), reflecting the maximum length of the input lists plus potentially one additional node for a carry in the sum. This accounts for the space needed to store the resultant list. In the context of big O notation and for simplification, this can be represented as O(n) or O(m), depending on which of the two lists is longer, indicating that the space complexity scales linearly with the size of the input.