Add Two Numbers in Python (Time Complexity: O(max(n, m)))

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.

Example 1:

Input: list1 = [2, 4, 3], list2 = [5, 6, 4]
Output: [7, 0, 8]
Explanation: 342 + 465 = 807

Example 2:

Input: list1 = [9,9,9,9,9,9,9], list2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Explanation: 9999999 + 9999 = 10009998

Understanding the Problem

The core challenge of this problem is to add two numbers represented by linked lists where each node contains a single digit. The digits are stored in reverse order, meaning the 1's digit is at the head of the list. This problem is significant in scenarios where numbers are too large to be handled by standard data types and need to be processed digit by digit.

Potential pitfalls include handling the carry-over during addition and ensuring the linked list is correctly formed without leading zeros (except for the number 0 itself).

Approach

To solve this problem, we can use a straightforward approach by iterating through both linked lists simultaneously, adding corresponding digits along with any carry from the previous addition. If one list is shorter, we continue with the longer list. The carry is managed throughout the process.

Here is a step-by-step approach:

Initialize a dummy node to act as the head of the result linked list.
Use a pointer to traverse the result list and a variable to keep track of the carry.
Iterate through both linked lists until both are exhausted.
For each pair of nodes, add their values along with the carry.
Update the carry for the next iteration.
Create a new node with the digit value of the current sum and attach it to the result list.
After the loop, if there is any remaining carry, add a new node with the carry value.

Algorithm

Here is a detailed breakdown of the algorithm:

Initialize a dummy node and a current pointer to build the result list.
Initialize a carry variable to 0.
Loop through both linked lists until both are None:
- Sum the values of the current nodes of both lists (if they exist) and the carry.
- Update the carry to be the integer division of the sum by 10.
- Create a new node with the value of the sum modulo 10 and attach it to the result list.
- Move the current pointer to the next node.
- Move to the next nodes in both input lists (if they exist).
If there is any carry left after the loop, create a new node with the carry value.
Return the next node of the dummy node as the head of the result list.

Code Implementation

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

def addTwoNumbers(l1, l2):
    # Initialize dummy node and current pointer
    dummy = ListNode()
    current = dummy
    carry = 0

    # Loop through both linked lists
    while l1 or l2 or carry:
        # Get the values of the current nodes (0 if None)
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0

        # Calculate the sum and update the carry
        total = val1 + val2 + carry
        carry = total // 10
        total = total % 10

        # Create a new node with the sum and attach to the result list
        current.next = ListNode(total)
        current = current.next

        # Move to the next nodes in the input lists
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next

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

Complexity Analysis

The time complexity of this approach is O(max(n, m)), where n and m are the lengths of the two linked lists. This is because we traverse both lists once. The space complexity is O(max(n, m)) as well, due to the space required for the result linked list.

Edge Cases

Potential edge cases include:

One list is longer than the other.
One list is empty.
All nodes result in a carry.
Both lists are empty (though the problem states they are non-empty).

Each of these cases is handled by the algorithm as it checks for None nodes and manages the carry appropriately.

Testing

To test the solution comprehensively, consider the following test cases:

Simple cases with no carry.
Cases with carry-over.
Cases where one list is longer than the other.
Edge cases with all nodes resulting in a carry.

Using a testing framework like unittest or pytest can help automate and validate these test cases.

Thinking and Problem-Solving Tips

When approaching such problems, consider breaking down the problem into smaller parts and handling each part step-by-step. Practice similar problems to improve your problem-solving skills and understand different ways to approach linked list problems.

Conclusion

In this blog post, we discussed how to add two numbers represented by linked lists. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving your algorithmic thinking and coding skills.

Additional Resources

For further reading and practice, consider the following resources: