LeetCode 2: Add Two Numbers

Problem Statement

LeetCode 2, Add Two Numbers, is a medium-level challenge that involves adding two numbers stored as linked lists. You’re given two non-empty linked lists, l1 and l2, where each node holds a single digit (0-9). The digits are in reverse order, meaning the first node is the ones place, the next is the tens place, and so on. The task is to add these numbers and return the sum as a new linked list in the same reverse-order format. The numbers won’t have leading zeros, except for zero itself (e.g., [0]).

Constraints

Number of nodes in each list: 1 to 100.
0 <= Node.val <= 9: Each node is a single digit.
No leading zeros in the numbers, except for 0 alone.
Input lists are non-empty.

Example

Input: l1 = [2, 4, 3], l2 = [5, 6, 4]
Output: [7, 0, 8]
Explanation: 342 + 465 = 807, so [7, 0, 8] is 807 in reverse order.

Input: l1 = [0], l2 = [0]
Output: [0]
Explanation: 0 + 0 = 0, so [0].

Input: l1 = [9, 9, 9, 9, 9, 9, 9], l2 = [9, 9, 9, 9]
Output: [8, 9, 9, 9, 0, 0, 0, 1]
Explanation: 9999999 + 9999 = 10009998, so [8, 9, 9, 9, 0, 0, 0, 1].

Understanding the Problem

Imagine adding two numbers like you do on paper, but the digits are flipped backward in linked lists. For example, l1 = [2, 4, 3] is 342 because 2 is the ones place, 4 is the tens, and 3 is the hundreds. We need to:

Add the digits step by step, starting from the ones place.
Handle carries (like when 9 + 9 = 18, you write 8 and carry 1).
Build a new linked list with the sum, keeping the reverse order.
Deal with lists of different lengths or extra carries at the end.

We’ll focus on one main solution:

Iterative: Adding digits step by step with a carry.

Solution: Iterative Approach

Explanation

This method works like regular addition, going digit by digit through the lists, keeping track of any carry, and building the answer list as we go. We use a “dummy” node to make building the list easier.

Initialize Variables.

Set up a dummy node to start the answer list, a pointer to build it, and a carry (starts at 0).

2. Traverse Both Lists.

While there are digits in either list or a carry left:

Get digits from l1 and l2 (use 0 if a list ends).
Add them with the carry.
Figure out the new digit (ones place) and new carry (tens place).
Make a new node with the digit.

3. Link Nodes.

Attach each new node to the growing list and move the pointer.

4. Return Result.

Skip the dummy node and return the real start of the answer.

Step-by-Step Example

Example 1: l1 = [2, 4, 3], l2 = [5, 6, 4], sum = 807

We have l1 = [2, 4, 3] (342) and l2 = [5, 6, 4] (465). Adding gives 807, so the answer should be [7, 0, 8].

Goal: Add the numbers digit by digit and build [7, 0, 8].
Result for reference: 342 + 465 = 807, which is [7, 0, 8] backward.
Start: Use a dummy node (say 0), set the builder pointer to it, and carry starts at 0.
Step 1: Ones place – l1 has 2, l2 has 5.

Add them: 2 + 5 + 0 (carry) = 7.
New digit is 7 (no tens), carry stays 0.
Make a node with 7, attach it after dummy, move pointer to 7.
Now: dummy -> 7, l1 moves to 4, l2 to 6.

Step 2: Tens place – l1 has 4, l2 has 6.

Add: 4 + 6 + 0 = 10.
New digit is 0 (ones part), carry becomes 1 (tens part).
Make a node with 0, attach after 7, move pointer to 0.
Now: dummy -> 7 -> 0, l1 moves to 3, l2 to 4.

Step 3: Hundreds place – l1 has 3, l2 has 4.

Add: 3 + 4 + 1 (carry) = 8.
New digit is 8, carry drops to 0.
Make a node with 8, attach after 0, move pointer to 8.
Now: dummy -> 7 -> 0 -> 8, both lists are done.

Step 4: Check – No digits left, carry is 0, so stop.
Result: Skip dummy, return [7, 0, 8].

Matches 807 backward, exactly what we wanted.

Example 2: l1 = [9, 9], l2 = [1], sum = 100

Now, l1 = [9, 9] (99) and l2 = [1] (1). Adding gives 100, so the answer is [0, 0, 1].

Goal: Add digit by digit to get [0, 0, 1].
Result for reference: 99 + 1 = 100, which is [0, 0, 1] backward.
Start: Dummy node, pointer at dummy, carry at 0.
Step 1: Ones place – l1 has 9, l2 has 1.

Add: 9 + 1 + 0 = 10.
Digit is 0, carry is 1.
Node with 0, attach after dummy, move pointer.
Now: dummy -> 0, l1 to 9, l2 done.

Step 2: Tens place – l1 has 9, l2 has no digits (use 0).

Add: 9 + 0 + 1 = 10.
Digit is 0, carry is 1.
Node with 0, attach after 0, move pointer.
Now: dummy -> 0 -> 0, l1 done.

Step 3: Extra carry – No digits left, but carry is 1.

Add: 0 + 0 + 1 = 1.
Digit is 1, carry is 0.
Node with 1, attach after 0, move pointer.
Now: dummy -> 0 -> 0 -> 1.

Step 4: Check – No digits, carry 0, stop.
Result: Skip dummy, return [0, 0, 1].

Matches 100 backward, perfect.

Code

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

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)
    current = dummy
    carry = 0

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

        total = val1 + val2 + carry
        carry = total // 10
        digit = total % 10

        current.next = ListNode(digit)
        current = current.next

        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None

    return dummy.next

Complexity

Time Complexity: O(max(N, M)) – Goes through the longer list once, where N and M are list lengths.
Space Complexity: O(max(N, M)) – Space for the answer list.

Efficiency Notes

This is efficient for linked lists, handling different lengths and carries naturally. It’s the standard way to solve this problem.

Alternative: Recursive Approach (Brief Mention)

Explanation

A recursive method could add digits by calling itself for each pair, passing the carry. It’s less common because it uses more stack space (O(max(N, M))) and is harder to follow, so we stick with iterative.

Additional Example

For l1 = [5, 6], l2 = [5, 4], sum = 110:

Goal: Get [0, 1, 1].
Result for reference: 65 + 45 = 110, so [0, 1, 1].
Step 1: 5 + 5 = 10, digit 0, carry 1, list: [0].
Step 2: 6 + 4 + 1 = 11, digit 1, carry 1, list: [0, 1].
Step 3: 0 + 0 + 1 = 1, digit 1, carry 0, list: [0, 1, 1].
Result: [0, 1, 1].

Edge Cases

Different Lengths: l1 = [9, 9], l2 = [1] – Uses 0 for missing digits.
Carry at End: l1 = [9], l2 = [1] – Adds extra node for carry.
Single Nodes: l1 = [0], l2 = [0] – Simple addition.

Final Thoughts

Iterative: Straightforward and efficient, great for learning linked lists.
Practice Value: Builds skills for list problems like merging or reversing.