Learning

Add Two Numbers

By Ashley

October 8, 2024

3 min read

Save

Add Two Numbers

Mastering the art of solving the "Add Two Numbers" problem is a fundamental skill for anyone delving into the world of algorithms and data structures. This problem, often encountered in coding interviews and competitive programming, involves adding two numbers represented by linked lists. Each node in the linked list represents a single digit of the number, and the digits are stored in reverse order. The challenge lies in efficiently adding these numbers while handling carry-over values.

Table of Contents

Understanding the Problem

The "Add Two Numbers" problem can be broken down into several key components:

Linked List Representation: Each number is represented as a linked list where each node contains a single digit. The digits are stored in reverse order, meaning the least significant digit is at the head of the list.
Carry-Over Handling: When adding two digits, if the sum exceeds 9, a carry-over value is generated, which needs to be added to the next pair of digits.
Edge Cases: Consider cases where the linked lists are of different lengths or where one of the lists is empty.

Approach to Solving the Problem

To solve the "Add Two Numbers" problem, we can follow a step-by-step approach:

Initialize Pointers: Start with pointers to the head of both linked lists and a dummy node to build the result list.
Iterate Through Lists: Traverse both lists simultaneously, adding corresponding digits and handling the carry-over.
Handle Remaining Digits: If one list is longer than the other, continue adding the remaining digits along with any carry-over.
Final Carry-Over: After traversing both lists, if there is any remaining carry-over, add a new node with this value.

Detailed Steps

Let's dive into the detailed steps to implement the solution:

Step 1: Define the ListNode Class

First, we need to define the structure of a node in the linked list. In most programming languages, this is done using a class or struct.

Here is an example in Python:

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

Step 2: Initialize Pointers

Create a dummy node to serve as the starting point of the result list. This helps in easily returning the head of the result list. Also, initialize pointers for both input lists and a variable to keep track of the carry-over.

dummy_head = ListNode(0)
current = dummy_head
carry = 0

Step 3: Iterate Through Lists

Use a loop to traverse both lists until you reach the end of both. In each iteration, add the corresponding digits along with the carry-over and update the carry-over for the next iteration.

while l1 or l2 or carry:
    val1 = l1.val if l1 else 0
    val2 = l2.val if l2 else 0

    # Calculate the sum and carry
    total = val1 + val2 + carry
    carry = total // 10
    current.next = ListNode(total % 10)
    current = current.next

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

💡 Note: The modulo operation (total % 10) ensures that only the last digit of the sum is stored in the current node, while the integer division (total // 10) calculates the carry-over.

Step 4: Return the Result

After the loop, the dummy node's next pointer will point to the head of the result list. Return this node as the result.

return dummy_head.next

Example Walkthrough

Let's walk through an example to solidify our understanding. Consider the following two linked lists:

List 1	List 2
2 -> 4 -> 3	5 -> 6 -> 4

These lists represent the numbers 342 and 465, respectively. Adding these numbers gives us 807. The result should be represented as a linked list: 7 -> 0 -> 8.

Here is how the algorithm processes this example:

Start with carry = 0.
Add 3 and 4, get 7 (carry = 0).
Add 4 and 6, get 10 (carry = 1).
Add 2 and 5, get 8 (carry = 1).
Add carry 1, get 1 (carry = 0).

The final result is 7 -> 0 -> 8.

Optimizing the Solution

While the above approach is efficient with a time complexity of O(max(m, n)), where m and n are the lengths of the two linked lists, there are a few optimizations we can consider:

Space Optimization: The solution uses O(1) extra space apart from the space required for the result list. This is optimal as we are not using any additional data structures.
Edge Case Handling: Ensure that the solution handles edge cases such as empty lists gracefully. The current implementation already handles this by checking if the lists are None.

Additionally, if the problem constraints allow, you can consider using recursion to solve the problem. However, this approach might not be as space-efficient due to the recursion stack.

Alternative Approaches

While the iterative approach is straightforward and efficient, there are alternative methods to solve the "Add Two Numbers" problem:

Recursive Approach: Use recursion to add the digits and handle the carry-over. This approach is more elegant but can be less efficient due to the recursion stack.
String Conversion: Convert the linked lists to strings, add the strings as numbers, and then convert the result back to a linked list. This approach is simple but less efficient due to the overhead of string operations.

Each approach has its own trade-offs, and the choice depends on the specific requirements and constraints of the problem.

Here is an example of the recursive approach in Python:

def addTwoNumbersRecursive(l1, l2, carry=0):
    if not l1 and not l2 and not carry:
        return None

    val1 = l1.val if l1 else 0
    val2 = l2.val if l2 else 0

    total = val1 + val2 + carry
    carry = total // 10
    current = ListNode(total % 10)

    if l1 or l2 or carry:
        current.next = addTwoNumbersRecursive(l1.next if l1 else None, l2.next if l2 else None, carry)

    return current

This recursive function adds the digits and handles the carry-over, returning the head of the result list.

💡 Note: The recursive approach is more elegant but can be less efficient due to the recursion stack. It is important to consider the depth of recursion and the potential for stack overflow in large inputs.

In conclusion, the “Add Two Numbers” problem is a classic example of how to manipulate linked lists and handle carry-over values efficiently. By understanding the problem, breaking it down into manageable steps, and implementing a solution, you can master this fundamental algorithm. Whether you choose an iterative or recursive approach, the key is to handle edge cases and optimize for both time and space complexity. This problem not only tests your algorithmic skills but also your ability to think logically and implement solutions efficiently.

Related Terms: