2. Add 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.

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

First Thoughts

Because the digits are already stored in reverse order, the lists can be processed from head to tail in the same order that normal addition is performed from right to left.

For each pair of nodes, I add their values along with any carry from the previous digit. If one list is shorter than the other, I treat the missing value as 0.

I use a dummy head node to simplify construction of the result list. A separate curr pointer always points to the last node that has been added.

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:


        carry = 0
        sol = ListNode()
        curr = sol

        while l1 is not None or l2 is not None:

            if(l1 is None):
                n1 = 0
            else:
                n1 = l1.val

            if(l2 is None):
                n2 = 0
            else:
                n2 = l2.val

            sum = n1 + n2 + carry
            carry = int(sum / 10)
            remainder = sum % 10

            curr.next = ListNode(remainder)

            curr = curr.next

            if l1 is not None:
                l1 = l1.next

            if l2 is not None:
                l2 = l2.next

        if carry != 0:
            curr.next = ListNode(carry)

        return sol.next

For example, if the current digits are 4 and 6 and the previous operation produced a carry of 1:

4 + 6 + 1 = 11

digit = 1
carry = 1

The digit 1 is appended to the result list, and the carry is used during the next iteration.

The loop continues until both input lists have been exhausted. If a carry remains afterward, one additional node is appended.

• Time: O(max(n, m))
• Space: O(max(n, m))

The additional working space, excluding the returned list, is O(1).

Improved Approach

The original approach is already optimal in terms of time complexity, but the implementation can be simplified.

Instead of explicitly checking whether each node is None, I can use conditional expressions to treat missing nodes as 0.

Python's divmod() also gives both the carry and the digit in one operation:

divmod(11, 10) -> (1, 1)

carry = 1
digit = 1

I can also include carry directly in the loop condition. This removes the need for a separate check after the loop.

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:

        carry = 0
        sol = ListNode()
        curr = sol

        while l1 or l2 or carry:

            n1 = l1.val if l1 else 0
            n2 = l2.val if l2 else 0

            carry, digit = divmod(n1 + n2 + carry, 10)

            curr.next = ListNode(digit)
            curr = curr.next

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

        return sol.next

Including carry in the loop condition handles cases where the final addition produces another digit.

For example:

l1 = [5]
l2 = [5]

5 + 5 = 10

The first iteration adds 0 to the result and leaves a carry of 1. Even though both lists are now exhausted, the remaining carry causes one final iteration that appends the 1.

Result: [0,1]

Both implementations have the same asymptotic complexity:

• Time: O(max(n, m))
• Space: O(max(n, m))

The improved version mainly reduces branching and makes the linked-list construction easier to follow.