Solving LeetCode's "Add Two Numbers" Iteratively and Recursively - Part 1

If you’ve spent any time preparing for software engineering interviews, you’ve likely come across LeetCode's Add Two Numbers. This problem is a classic, frequently asked by top tech companies because it’s a perfect test of your understanding of recursion, linked lists and basic arithmetic logic.

In this article, we’ll break down this problem step-by-step. We won't just look at one solution, but two powerful approaches: a straightforward iterative method and an elegant recursive one.

Breaking Down the Problem

First, let's understand the task. We are given two non-empty linked lists, where each node contains a single digit. The digits are stored in reverse order. Our job is to add the two numbers together and return the result as a new linked list.

For example, if the inputs are l1 = [2,4,3] and l2 = [5,6,4], this represents the numbers 342 and 465. The sum is 807, which should be returned as the linked list [7,0,8].

The key insight here is that the reverse order makes our job much easier. It mimics how we do addition by hand—starting from the rightmost digit and moving left, keeping track of a carry value.

So, the core challenges are:

1. Traverse both linked lists simultaneously.
2. Handle cases where one list is longer than the other.
3. Correctly calculate and manage the carry at each step.
4. Construct the new result linked list as we go.

Solution 1: The Iterative Approach (The Workhorse)

The most direct way to solve this is with a while loop. We'll iterate through the lists as long as there are digits left in either l1 or l2, or if there's a carry left over from the last calculation.

A common and very useful pattern here is to use a dummyNode. This node acts as a placeholder for the head of our new list, simplifying the code so we don't have to handle the first node as a special case.

Here is the complete iterative solution in Python:

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

        while l1 or l2 or carry != 0:
            # Get the values, using 0 if a list is exhausted
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0

            # Perform the addition
            total_sum = val1 + val2 + carry
            carry = total_sum // 10
            digit = total_sum % 10

            # Create the new node and advance our pointer
            current.next = ListNode(digit)
            current = current.next

            # Advance the list pointers
            if l1: l1 = l1.next
            if l2: l2 = l2.next

        return dummyNode.next

Here is the explanation of iterative solution:

• Initialization: We create a dummyNode to anchor our result list and a current pointer to build it. carry starts at 0.

• The Loop: The loop continues as long as l1, l2, or carry has a value. This elegantly handles different list lengths and the final carry (like in 9 + 9 = 18).

• Value Extraction: val1 = l1.val if l1 else 0 is a clean way to handle one list being longer than the other. If a list is None, we just use 0 for the calculation.

• Building the Result: We create a new ListNode with the calculated digit and attach it to our result list.

• Return Value: We return dummyNode.next, which is the true head of our new list.

Solution 2: The Recursive Approach (The Elegant Alternative)

Recursion can often lead to more concise and declarative code. The problem can be rephrased recursively:

The sum of two linked lists is a new node with the sum of the current digits, whose next pointer is the sum of the rest of the lists.

This maps perfectly to a recursive function.

Here is the recursive solution:

class Solution(object):
    def addTwoNumbers(self, l1, l2, carry=0):
        # Base Case: stop when there are no more nodes and no carry
        if not l1 and not l2 and not carry:
            return None

        # Get the values, using 0 if a node is None
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0

        # Perform the addition
        total_sum = val1 + val2 + carry
        carry = total_sum // 10
        digit = total_sum % 10

        # Create the new node for the current digit
        newNode = ListNode(digit)

        # Recursive Step: call the function for the next nodes
        next_l1 = l1.next if l1 else None
        next_l2 = l2.next if l2 else None
        newNode.next = self.addTwoNumbers(next_l1, next_l2, carry)

        return newNode

Here is the explanation of recursive solution:

• Base Case: The recursion stops when both lists are exhausted (None) and there is no carry left to add. This is the most crucial part of any recursive solution.

• Recursive Step: For the current call, we calculate the sum and digit just like in the iterative version. We create a newNode with this digit. The magic happens next: we set newNode.next to the result of calling the function again with the next nodes and the new carry.

Comparing the Approaches

Time Complexity is the same(O(n)) for both because we must visit each node in the longer list at least once.

Space Complexity is the key difference. The iterative solution uses a constant(O(1)) amount of extra space for the dummyNode, current, and carry variables. The recursive solution, however, creates a new stack frame for each call, so the space(O(n)) it uses is proportional to the length of the longest list. For very large lists, this could theoretically lead to a stack overflow error.

Conclusion

The Add Two Numbers problem is a fantastic exercise for mastering recursion and linked list manipulation. By implementing both an iterative and a recursive solution, we can appreciate the different ways to approach the same problem and understand their unique trade-offs in terms of space and readability.

Which solution do you prefer? Let me know in the comments! Happy coding.