Problem Description

You need to add two non-negative integers that are represented as linked lists. The key characteristics of this problem are:

1. Input Format: Two linked lists where each node contains a single digit (0-9)

2. Digit Storage: The digits are stored in reverse order, meaning the ones place is at the head of the list

   • For example: The number 342 would be represented as 2 -> 4 -> 3
   • The number 465 would be represented as 5 -> 6 -> 4

3. Task: Add these two numbers and return the sum as a new linked list (also in reverse order)

   • Using the example above: 342 + 465 = 807, which should be returned as 7 -> 0 -> 8

4. Constraints:

   • Both linked lists are non-empty
   • The numbers don't have leading zeros (except for the number 0 itself)

The solution simulates the grade-school addition algorithm. We traverse both linked lists simultaneously from head to tail, adding corresponding digits along with any carry from the previous position. The process continues until both lists are exhausted and there's no remaining carry.

The algorithm handles lists of different lengths by treating missing nodes as having a value of 0. For each position, it:

• Calculates the sum: current_digit_l1 + current_digit_l2 + carry
• Determines the new digit: sum % 10
• Updates the carry: sum // 10
• Creates a new node with the calculated digit and adds it to the result list

Intuition

The key insight is recognizing that the linked lists store digits in reverse order, which actually makes the addition process more natural. When we add numbers by hand, we start from the rightmost digit (ones place) and move left, carrying over when needed. Since our linked lists already start with the ones place at the head, we can directly simulate this addition process.

Think about how you would add 342 + 465 on paper:

  342
+ 465
-----
  807

You'd start from the right: 2 + 5 = 7, then 4 + 6 = 10 (write 0, carry 1), then 3 + 4 + 1 = 8.

With our reversed linked lists (2->4->3 and 5->6->4), we can traverse from head to tail and perform the exact same operations in the same order. This eliminates the need to reverse the lists first or use extra space to store intermediate results.

The elegance of this approach comes from handling three cases uniformly:

1. When both lists have digits to process
2. When one list is longer than the other (treat missing digits as 0)
3. When we have a final carry after processing all digits (like when adding 99 + 1 = 100)

By using a dummy head node, we avoid special-casing the creation of the first node in our result list. The while l1 or l2 or carry condition ensures we continue as long as there's any work left to do, whether it's processing remaining digits from either list or handling a final carry.

Learn more about Recursion, Linked List and Math patterns.

Solution Approach

The solution uses a simulation approach to add the two numbers digit by digit, just like manual addition. Here's how the implementation works:

Data Structure Setup:

• Create a dummy node to simplify list construction (avoids special handling for the first node)
• Initialize carry = 0 to track carry-over between digit additions
• Set curr pointer to dummy to track where we're building the result list

Main Algorithm Loop: The while l1 or l2 or carry condition ensures we continue processing as long as:

• There are digits remaining in l1, OR
• There are digits remaining in l2, OR
• There's a carry value that needs to be added

For each iteration:

1. Calculate the sum:

   s = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry

   This safely handles cases where one list is shorter by treating missing nodes as 0

2. Extract digit and carry:

   carry, val = divmod(s, 10)

   divmod(s, 10) returns (quotient, remainder), giving us the new carry and the digit to store

3. Build the result:

   curr.next = ListNode(val)
   curr = curr.next

   Create a new node with the calculated digit and advance our pointer

4. Advance input pointers:

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

   Move to the next digit in each list if available

Return Result: Return dummy.next to skip the dummy head and provide the actual result list.

Time Complexity: O(max(m, n)) where m and n are the lengths of the two input lists Space Complexity: O(max(m, n)) for the new linked list storing the result

Example Walkthrough

Let's walk through adding 342 + 465 = 807 step by step.

Input Lists:

• l1: 2 -> 4 -> 3 (represents 342)
• l2: 5 -> 6 -> 4 (represents 465)

Initial Setup:

• Create dummy node (placeholder head)
• carry = 0
• curr points to dummy

Iteration 1:

• Both lists have nodes: l1.val = 2, l2.val = 5
• Calculate sum: 2 + 5 + 0 = 7
• carry = 7 // 10 = 0, digit = 7 % 10 = 7
• Create new node with value 7, attach to result
• Advance: l1 to 4, l2 to 6
• Result so far: dummy -> 7

Iteration 2:

• Both lists have nodes: l1.val = 4, l2.val = 6
• Calculate sum: 4 + 6 + 0 = 10
• carry = 10 // 10 = 1, digit = 10 % 10 = 0
• Create new node with value 0, attach to result
• Advance: l1 to 3, l2 to 4
• Result so far: dummy -> 7 -> 0

Iteration 3:

• Both lists have nodes: l1.val = 3, l2.val = 4
• Calculate sum: 3 + 4 + 1 = 8
• carry = 8 // 10 = 0, digit = 8 % 10 = 8
• Create new node with value 8, attach to result
• Advance: l1 to None, l2 to None
• Result so far: dummy -> 7 -> 0 -> 8

Iteration 4:

• Both l1 and l2 are None, carry = 0
• Loop condition (l1 or l2 or carry) is False, exit loop

Final Result: Return dummy.next which gives us 7 -> 0 -> 8 (represents 807)

This correctly computes 342 + 465 = 807.

Solution Implementation

Time and Space Complexity

Time Complexity: O(max(m, n)), where m and n are the lengths of the two linked lists l1 and l2 respectively. The algorithm traverses both linked lists simultaneously until both are exhausted and there's no carry. In each iteration, we perform constant time operations (addition, modulo, division, and node creation), so each position requires O(1) time. The total number of iterations is at most max(m, n) + 1 (the +1 accounts for a potential final carry), which simplifies to O(max(m, n)).

Space Complexity: O(max(m, n)) for the output linked list that stores the result, which will have at most max(m, n) + 1 nodes. However, if we don't count the space used for the output (as it's required for the answer), the auxiliary space complexity is O(1) since we only use a constant amount of extra space for variables like dummy, carry, and curr.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle the Final Carry

One of the most common mistakes is forgetting that after processing all digits from both lists, there might still be a carry that needs to be added as a new node.

Incorrect Implementation:

while l1 or l2:  # Missing carry check!
    s = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
    carry, val = divmod(s, 10)
    curr.next = ListNode(val)
    curr = curr.next
    l1 = l1.next if l1 else None
    l2 = l2.next if l2 else None
# If carry is 1 here, it's lost!

Example where this fails:

• Input: l1 = [9, 9] (represents 99), l2 = [1] (represents 1)
• Expected: [0, 0, 1] (represents 100)
• Incorrect result: [0, 0] (represents 00, missing the final carry)

Solution: Always include carry in the loop condition: while l1 or l2 or carry:

2. Modifying Input Lists Instead of Creating New Nodes

Some implementations try to reuse nodes from the input lists, which can cause issues if the original lists need to be preserved.

Problematic Approach:

# Trying to modify l1 in place
while l1 or l2 or carry:
    s = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
    carry, val = divmod(s, 10)
    if l1:
        l1.val = val  # Modifying original list!
        curr = l1
    else:
        curr.next = ListNode(val)
        curr = curr.next
    # ... rest of logic

Solution: Always create new ListNode objects for the result to keep the input lists unchanged.

3. Incorrectly Handling Lists of Different Lengths

Failing to properly handle cases where one list is shorter than the other.

Common Mistake:

while l1 and l2:  # Only processes while BOTH have nodes
    s = l1.val + l2.val + carry
    # ... process
    l1 = l1.next
    l2 = l2.next

# Then trying to handle remaining nodes separately - error prone!
while l1:
    s = l1.val + carry
    # ... duplicate logic
while l2:
    s = l2.val + carry
    # ... more duplicate logic

Solution: Use a single loop with conditional checks: (l1.val if l1 else 0) + (l2.val if l2 else 0)

4. Not Using a Dummy Head Node

Trying to handle the first node as a special case leads to complex and error-prone code.

Without Dummy Head:

result = None
curr = None
while l1 or l2 or carry:
    # ... calculate val
    new_node = ListNode(val)
    if result is None:  # Special handling for first node
        result = new_node
        curr = result
    else:
        curr.next = new_node
        curr = curr.next
    # ...
return result

Solution: Using a dummy head simplifies the logic significantly and eliminates special case handling.