LeetCode #2 solution: Adding two numbers

Problem: #2 adding two numbers

LeetCode #2 solution – Adding Two Numbers: 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.

Adding zeros:

Input: l1 = [0], l2 = [0]
Output: [0]

Different length:

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.

---

LeetCode #2 Solution – Adding Two Numbers

Problem Explanation

In this problem, we’re given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, meaning the 1’s digit is at the head of the list. Each node contains a single digit (0-9). Our task is to add the two numbers and return the sum as a linked list, also in reverse order.

For example:

• Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
• Output: 7 -> 0 -> 8
• Explanation: 342 + 465 = 807, and 807 reversed is 708.

Naive Approach: Converting to Integers

One might think of converting each linked list to its integer representation, performing the addition, and then converting the result back to a linked list.

Time Complexity: O(n + m), where n and m are the lengths of the lists.
Space Complexity: O(1) for computation, but O(k) for the resulting linked list.

def addTwoNumbers(l1, l2):
    num1 = num2 = 0
    multiplier = 1
    while l1:
        num1 += l1.val * multiplier
        l1 = l1.next
        multiplier *= 10
    multiplier = 1
    while l2:
        num2 += l2.val * multiplier
        l2 = l2.next
        multiplier *= 10
    total = num1 + num2
    # Convert total back to a linked list

Why This Might Fail on LeetCode:

• Integer Overflow: The linked lists can represent very large numbers (up to 100 digits), which may exceed the maximum value of integers in some languages.
• Not Handling Carries Properly: This method doesn’t take advantage of the linked list structure to handle carries digit by digit.

Optimal Approach: Digit-by-Digit Addition

A better approach is to simulate the addition as we would do it by hand:

1. Initialize a dummy head for the result linked list.
2. Traverse both lists simultaneously.
3. Add corresponding digits along with any carry from the previous addition.
4. Create a new node with the computed digit and attach it to the result list.
5. Update the carry for the next iteration.
6. After traversing both lists, if there’s a remaining carry, add a new node with that value.

Algorithm Benefits:

• No Integer Overflow: Since we’re dealing with one digit at a time, we avoid large number computations.
• Efficient: Only one pass through each list.

Time Complexity: O(max(n, m))
Space Complexity: O(max(n, m)) for the resulting linked list.

Ideal Data Structure and Algorithm

Using Linked Lists and Elementary Mathematics (addition with carry) is ideal for this problem. This approach aligns well with the data structure provided and handles large numbers gracefully.

Success on LeetCode:

• Handles Large Numbers: By processing one digit at a time, we avoid limitations related to integer sizes.
• Efficient Traversal: Only a single pass through the lists is needed.

Introduction to the Optimal Solution

The optimal solution involves simulating the addition process digit by digit, much like how we add numbers on paper. We’ll traverse both linked lists, add corresponding digits along with any carry, and build a new linked list for the result. This method is efficient and leverages the linked list structure effectively.

Step-by-Step Solution for LeetCode #2 problem

Let’s dive into the implementation:

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

class Solution:
    def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
        # Initialize a dummy node to simplify edge cases
        dummy = ListNode()
        current = dummy
        carry = 0
        
        # Traverse both lists until both are exhausted
        while l1 or l2 or carry:
            # If one of the lists is shorter, use 0 as its value
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            
            # Calculate the sum of the two digits and the carry
            total = val1 + val2 + carry
            carry = total // 10  # Carry for the next step
            total = total % 10   # Current digit to store
            
            # Create a new node with the sum of the two digits
            current.next = ListNode(total)
            current = current.next
            
            # Move to the next nodes in the lists
            if l1: l1 = l1.next
            if l2: l2 = l2.next
        
        return dummy.next

Step-by-Step Explanation:

1. Initialize dummy node: We create a dummy node to serve as the head of the result linked list. This simplifies handling edge cases where the result might be empty.
2. Loop through lists: We iterate through l1 and l2 until both are exhausted. During each iteration, we:
   • Add the corresponding digits from l1 and l2. If one list is shorter, we use 0 as the value.
   • Add the carry (if any) from the previous step.
   • Calculate the new carry and the digit for the current position.
3. Create new node: We create a new node with the calculated sum and attach it to the result linked list.
4. Handle carry: If there’s any carry left after the main loop, we create a final node for it.
5. Return the result: Finally, we return the linked list starting from dummy.next.

Optimization Tips

• Using a Dummy Head: Simplifies code by handling edge cases (e.g., empty lists) and avoids checking if the head is None.
• Efficient Carry Handling: By updating the carry each time, we avoid extra iterations after the main loop.
• Avoiding Repeated Calculations: Sum and carry are calculated once per iteration, minimizing computations.
• Pythonic Code: Use clear variable names and concise logic to make the code readable and maintainable.

Conclusion

By simulating the addition process digit by digit and leveraging the linked list data structure, we can efficiently add two numbers represented by linked lists. This approach is both effective and scalable, handling large numbers without any issues related to integer overflow.

---

Happy coding!

Continue to challenge yourself with more problems, and don’t hesitate to revisit and refine your solutions as you learn new techniques.

---

Looking for more LeetCode solutions? Stay tuned for upcoming guides on tackling other LeetCode challenges in Python. Whether you’re preparing for technical interviews or aiming to improve your coding skills, exploring a variety of problems will enhance your understanding and proficiency.

You can find this problem on LeedCode, click here.