Solving the ‘Add Two Numbers’ Problem on LeetCode — Python Solutions Walkthrough

Image Source

Introduction

The ‘Add Two Numbers’ problem on LeetCode involves adding two non-empty linked lists representing two non-negative integers. Each list’s digits are stored in reverse order, and each node contains a single digit. The task is to add the two numbers and return the sum as a linked list.

Python’s dynamic typing and powerful data structures make it well-suited for handling linked list problems efficiently. This article provides a detailed walkthrough of three distinct Python solutions to tackle the ‘Add Two Numbers’ problem. By the end of this guide, you will understand the mechanics behind each approach and their efficiency and effectiveness. Code comments and detailed step-by-step explanations for each method are provided after the conclusion.

Problem Description

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

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.

Function Signature in Python:

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """

Example 1:

Image Source

• 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]

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.

Solution 1: Iterative Approach with Carry Handling

This simple approach involves iterating through both linked lists, summing corresponding digits, and managing the carry for sums greater than 9.

Python Code:

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        dummy = ListNode(0)
        current = dummy
        carry = 0

        while l1 is not None or l2 is not None:
            x = l1.val if l1 is not None else 0
            y = l2.val if l2 is not None else 0
            sum = carry + x + y
            carry = sum // 10
            current.next = ListNode(sum % 10)
            current = current.next

            if l1 is not None: l1 = l1.next
            if l2 is not None: l2 = l2.next

        if carry > 0:
            current.next = ListNode(carry)

        return dummy.next

Time and Space Complexity

• Time Complexity: O(n), the algorithm traverses both linked lists l1 and l2 exactly once. In each iteration, it processes one node from each list and performs a constant amount of work (addition, carry handling, and node creation). Therefore, the time complexity is linear relative to the length of the longer list.
• Space Complexity: O(n), the space complexity is determined by the space required to store the result linked list. Since a new node is created for each digit of the sum, the space complexity is proportional to the length of the resulting list, which is O(n). The auxiliary space used for variables such as carry, dummy, and current is constant (O(1)), but the new linked list accounts for the overall O(n) space complexity.

Solution 2: Recursive Approach

This approach uses recursion to handle the addition of digits and carry, simplifying the iterative logic by breaking it down into smaller recursive calls.

Python Code:

class Solution(object):
    def addTwoNumbers(self, l1, l2, carry=0):
        if not l1 and not l2 and not carry:
            return None

        sum = carry
        if l1:
            sum += l1.val
            l1 = l1.next
        if l2:
            sum += l2.val
            l2 = l2.next

        result = ListNode(sum % 10)
        result.next = self.addTwoNumbers(l1, l2, sum // 10)
        return result

Time and Space Complexity

• Time Complexity: O(n), similar to the iterative approach, the recursive solution processes each node of the input lists once. Each recursive call handles one digit addition and proceeds to the next nodes of l1 and l2, making the time complexity linear in relation to the length of the longer list.
• Space Complexity: O(n), the space complexity includes both the space for the new linked list and the recursive call stack. Each recursive call consumes stack space, which leads to O(n) space complexity due to recursion depth being equal to the length of the longer list. Additionally, the new linked list created to store the result contributes to O(n) space complexity. Thus, the total space complexity is O(n) for both the call stack and the new linked list.

Solution 3: Optimized Iterative Approach with Pre-Allocated Nodes

This approach optimizes space usage by pre-allocating nodes for the result linked list and reusing nodes from the input lists wherever possible.

Python Code:

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        dummy = ListNode(0)
        current = dummy
        carry = 0

        while l1 is not None or l2 is not None:
            x = l1.val if l1 is not None else 0
            y = l2.val if l2 is not None else 0
            sum = carry + x + y
            carry = sum // 10

            current.next = l1 if l1 is not None else l2
            current.next.val = sum % 10

            current = current.next
            if l1 is not None: l1 = l1.next
            if l2 is not None: l2 = l2.next

        if carry > 0:
            current.next = ListNode(carry)

        return dummy.next

Time and Space Complexity

• Time Complexity: O(n), the optimized iterative approach also processes each node of l1 and l2 exactly once. Each iteration involves constant-time operations, such as value extraction, sum computation, carry handling, and node reassignment. As a result, the time complexity is linear (O(n)) with respect to the length of the longer list.
• Space Complexity: O(1), this approach optimizes space usage by reusing existing nodes from the input lists instead of creating new nodes. The only additional space required is for a few auxiliary variables (dummy, current, p, q, and carry), which do not depend on the input size. Consequently, the space complexity is constant (O(1)), making this approach more space-efficient compared to the other solutions.

Conclusion and Comparison

On analysis, all three Python methods demonstrate similar time complexities, as each involves a single traversal of the input linked lists. The space complexity varies across the solutions due to different strategies for handling the result linked list and carry.

Solution 1: Iterative Approach with Carry Handling

• Pros: This approach is straightforward and easy to understand. It efficiently handles the addition of two numbers by iterating through the lists and managing the carry within a loop. The logic is clear and simple, making it easy to implement and debug.
• Cons: It requires the creation of a new linked list to store the result, which results in a space complexity of O(n). This approach is less space-efficient compared to the optimized iterative solution.

Solution 2: Recursive Approach

• Pros: The recursive approach provides an elegant and concise solution to the problem. It simplifies the iterative logic by breaking it down into smaller, manageable recursive calls. The code is clean and easy to follow, making it a good choice for those who prefer recursion.
• Cons: The recursive approach has a higher space complexity due to the recursion stack, which can lead to O(n) space usage. This can be a limitation for very large input sizes, as it may cause stack overflow issues.

Solution 3: Optimized Iterative Approach with Pre-Allocated Nodes

• Pros: This solution is the most space-efficient as it reuses existing nodes from the input lists wherever possible. By pre-allocating nodes and updating their values, it minimizes additional space usage, achieving a space complexity of O(1). This approach is ideal for handling large input sizes without excessive memory consumption.
• Cons: The logic for node management is slightly more complex compared to the other solutions. It requires careful handling of node pointers and values, which can make the implementation more error-prone and harder to debug.

Summary

• Solution 1: Iterative Approach with Carry Handling provides a balance between simplicity and efficiency, making it a good starting point for understanding the problem.
• Solution 2: Recursive Approach offers a clean and elegant solution, but its higher space complexity can be a limitation for large inputs.
• Solution 3: Optimized Iterative Approach with Pre-Allocated Nodes is the most space-efficient and suitable for large input sizes, though it requires careful implementation.

While the second solution offers elegance and the first is a straightforward approach, the third solution provides the best combination of efficiency and space optimization. The use of node reuse in Solution 3 reflects a practical approach to handling linked list operations, which is often preferred in software development for its memory efficiency and effectiveness.

• LeetCode — Add Two Numbers
• Python Documentation

Thank you for reading! If you find this guide helpful, please consider highlighting, clapping, responding or connecting with me on Twitter/X as it’s very appreciated and helps keep content like this free!

Also check out my other Leetcode Walkthrough Lists:

• Two Sum Problem
• Palindrome Number Problem

Commented Code and Step-by-Step Explanations

Solution 1: Iterative Approach with Carry Handling

In this approach, we use an iterative method to traverse the input linked lists. We maintain a running sum of the digits and handle the carry for sums greater than 9. This solution iterates through both linked lists, adding corresponding digits along with any carry from the previous step. If the sum of the digits exceeds 9, the carry is updated accordingly. A new linked list is created to store the result, with each node representing a digit of the sum. This method makes sure that all digits are processed correctly, including the final carry if it exists.

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        dummy = ListNode(0)  # Create a dummy node to serve as the head of the result list
        current = dummy  # Initialize a pointer to build the result list
        carry = 0  # Initialize the carry to 0

        while l1 is not None or l2 is not None:  # Traverse both lists
            x = l1.val if l1 is not None else 0  # Get the value of the current node in l1, or 0 if l1 is null
            y = l2.val if l2 is not None else 0  # Get the value of the current node in l2, or 0 if l2 is null
            sum = carry + x + y  # Calculate the sum of the current values and the carry
            carry = sum // 10  # Update the carry
            current.next = ListNode(sum % 10)  # Create a new node with the digit value and link it to the result list
            current = current.next  # Move to the next node in the result list

            if l1 is not None: l1 = l1.next  # Move to the next node in l1
            if l2 is not None: l2 = l2.next  # Move to the next node in l2

        if carry > 0:  # If there is a remaining carry, create a new node for it
            current.next = ListNode(carry)

        return dummy.next  # Return the head of the result list

Step-by-Step Explanation

Step 1: Initialize a dummy node to serve as the head of the result list and a current pointer to build the result list. Initialize carry to 0.

Step 2: Traverse l1 and l2 simultaneously.

Step 3: Extract the values of the current nodes (x and y). If a list has been fully traversed, use 0 as the value.

Step 4: Compute the sum of the current values and the carry.

Step 5: Determine the new carry by dividing the sum by 10.

Step 6: Create a new node with the value of sum % 10 and link it to the result list.

Step 7: Move the current pointer to the new node.

Step 8: After exiting the loop, check if there is any remaining carry. If so, create a new node with the carry value and link it to the result list.

Step 9: Return the next of the dummy node as the head of the result list.

Solution 2: Recursive Approach

This approach uses recursion to handle the addition of digits and carry, simplifying the iterative logic by breaking it down into smaller recursive calls. At each step, the function processes one digit from each input list, adds them along with the carry, and recursively proceeds to the next nodes. The base case for the recursion handles the situation where both input lists are null and no carry remains. This method leverages the call stack to manage the state, which can make the code more elegant and concise, especially for those who prefer a recursive solution.

class Solution(object):
    def addTwoNumbers(self, l1, l2, carry=0):
        if not l1 and not l2 and not carry:  # Base case: if all are null and no carry, return null
            return None

        sum = carry  # Start with the carry value
        if l1:
            sum += l1.val  # Add the value of the current node in l1, if present
            l1 = l1.next
        if l2:
            sum += l2.val  # Add the value of the current node in l2, if present
            l2 = l2.next

        result = ListNode(sum % 10)  # Create a new node with the digit value
        result.next = self.addTwoNumbers(l1, l2, sum // 10)  # Recursive call with the next nodes and carry
        return result  # Return the result node

Step-by-Step Explanation

Step 1: Base case: If both l1 and l2 are null and there is no carry, return null.

Step 2: Add the values of the current nodes (l1 and l2) and the carry.

Step 3: Calculate the sum and the new carry.

Step 4: Create a new node with the value of sum % 10.

Step 5: Recursively call the function with the next nodes of l1 and l2, passing the new carry.

Step 6: Link the result of the recursive call to the next of the new node.

Step 7: Return the newly created node.

Solution 3: Optimized Iterative Approach with Pre-Allocated Nodes

This approach optimizes space usage by pre-allocating nodes for the result linked list and reusing nodes from the input lists wherever possible. Instead of creating new nodes for the result, this method updates and reuses the existing nodes from the input lists. This not only reduces the space complexity but also minimizes the overhead associated with dynamic memory allocation. By carefully managing node pointers and values, this solution achieves efficient memory usage while correctly handling the addition and carry operations.

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        dummy = ListNode(0)  # Create a dummy node to serve as the head of the result list
        current = dummy  # Initialize a pointer to build the result list
        carry = 0  # Initialize the carry to 0

        while l1 is not None or l2 is not None:  # Traverse both lists
            x = l1.val if l1 is not None else 0  # Get the value of the current node in l1, or 0 if l1 is null
            y = l2.val if l2 is not None else 0  # Get the value of the current node in l2, or 0 if l2 is null
            sum = carry + x + y  # Calculate the sum of the current values and the carry
            carry = sum // 10  # Update the carry

            current.next = l1 if l1 is not None else l2  # Reuse the current node of l1 or l2
            current.next.val = sum % 10  # Update the node's value to the digit value

            current = current.next  # Move to the next node in the result list
            if l1 is not None: l1 = l1.next  # Move to the next node in l1
            if l2 is not None: l2 = l2.next  # Move to the next node in l2

        if carry > 0:  # If there is a remaining carry, create a new node for it
            current.next = ListNode(carry)

        return dummy.next  # Return the head of the result list

Step-by-Step Explanation

Step 1: Initialize a dummy node to serve as the head of the result list and a current pointer to build the result list. Initialize carry to 0.

Step 2: Traverse l1 and l2 simultaneously.

Step 3: Extract the values of the current nodes (x and y). If a list has been fully traversed, use 0 as the value.

Step 4: Compute the sum of the current values and the carry.

Step 5: Determine the new carry by dividing the sum by 10.

Step 6: Instead of creating a new node, reuse the current nodes of l1 or l2 by updating their values to sum % 10.

Step 7: Link the reused node to the result list.

Step 8: Move the current pointer to the reused node.

Step 9: After exiting the loop, check if there is any remaining carry. If so, create a new node with the carry value and link it to the result list.

Step 10: Return the next of the dummy node as the head of the result list.