Here is solutions for Add Two Numbers.

1. Understand the problem

• You’re given two non-empty singly linked lists representing two non-negative integers.

• Each node contains a single digit (0–9).

• The digits are stored in reverse order: e.g. list 2 -> 4 -> 3 represents the number 342.

• You must add the two numbers and return the sum as a linked list, in the same reversed format.

Example:

l1 = 2 -> 4 -> 3 (342)
l2 = 5 -> 6 -> 4 (465)
Sum = 807 → output: 7 -> 0 -> 8.

2. Clarify constraints (4–5 questions + assumptions)

1. Can the linked lists have different lengths?

• Yes. Assume they can, e.g. l1 = 2 -> 4, l2 = 5 -> 6 -> 4.

1. Can there be a carry that extends beyond the longer list (e.g. 999 + 1 = 1000)?

• Yes. If there is a final carry, you must create a new node for it.

1. Are the input numbers always non-negative? Any negative digits?

• Assume non-negative integers only; each node’s value is in [0, 9].

1. Can the input be empty lists (None)?

• LeetCode usually gives non-empty lists, but your code should gracefully handle None (treated as 0).

1. Do we need to modify the original lists, or create a new one?

• You can create a new list (the usual approach). Modifying inputs isn’t required.

1. Time / memory constraints:

• n = length of l1, m = length of l2

• Aim for O(n + m) time and O(1) extra space (excluding the output list).

3. Explore examples

• Example 1 (classic):

l1 = 2 -> 4 -> 3 (342)
l2 = 5 -> 6 -> 4 (465)
342 + 465 = 807 → output: 7 -> 0 -> 8.

• Example 2 (different lengths, no final carry)

l1 = 9 -> 9 (99)
l2 = 1 (1)
99 + 1 = 100 → output: 0 -> 0 -> 1.

• Example 3 (single node, with final carry)

l1 = 5
l2 = 7
5 + 7 = 12 → output: 2 -> 1.

• Example 4 (one list is effectively 0)

l1 = 0
l2 = 0
0 + 0 = 0 → output: 0.

4. Brainstorm 2–3 solutions

4.1. Naive Solution - Convert to integers - Time O(N + M), Space O(N + M)

Idea:

• Convert l1 to an integer num1 by traversing and using place values.

• Convert l2 to integer num2.

• Compute total = num1 + num2.

• Convert total back into a linked list in reverse order.

Complexity:

• Time: O(N + M).

• Space: O(N).

4.2. Solution 2 (Optimal, iterative with carry) – standard approach - Time O(N + M), Space O(1)

• Use a pointer for each list: p1 for l1, p2 for l2.

• Maintain a carry variable (0 or 1 or maybe up to 9 + 9 + carry = 19, but we only keep 0–1 in decimal addition).

• At each step:

Take x = p1.val if p1 exists, else 0.

Take y = p2.val if p2 exists, else 0.

sum = x + y + carry.

New digit = sum % 10, new carry = sum // 10.

Append a new node with value sum % 10 to the result list.

Move p1 and p2 forward if possible.

• After finishing both lists, if carry > 0, append a final node.

• Complexity:

  • Time: O(N + M).

  • Space: O(1).

4.3. Solution 3 (Recursive with carry) - Time O(N + M), Space O(N + M)

Same logic as Solution 2, but implemented recursively:

• Base case: no nodes in both lists and carry is 0 → return None.

Otherwise:

• Calculate sum = val1 + val2 + carry.

• Current node = sum % 10.

• Recurse on next1, next2, and carry = sum // 10.

• Time: O(N + M)

• Space: O(N + M)

5. Implement solutions

5.1. Naive Solution - Time O(N + M), Space O(N + M)

class SolutionNaive:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        def to_int(node: ListNode) -> int:
            num = 0
            place = 1
            while node:
                num += node.val * place
                place *= 10
                node = node.next
            return num

        num1 = to_int(l1)
        num2 = to_int(l2)
        total = num1 + num2

        if total == 0:
            return ListNode(0)

        dummy = ListNode()
        current = dummy
        while total > 0:
            current.next = ListNode(total % 10)
            current = current.next
            total //= 10

        return dummy.next

• Time: O(N + M)

• Space: O(N + M)

5.2. Recursion Idea - Time O(N + M), Space O(N + M)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def add(self, l1: Optional[ListNode], l2: Optional[ListNode], carry: int) -> Optional[ListNode]:
        if not l1 and not l2 and carry == 0:
            return None

        v1 = l1.val if l1 else 0
        v2 = l2.val if l2 else 0

        carry, val = divmod(v1 + v2 + carry, 10)

        next_node = self.add(
            l1.next if l1 else None,
            l2.next if l2 else None,
            carry
        )
        return ListNode(val, next_node)

    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        return self.add(l1, l2, 0)

• Time: O(N + M).

• Space: O(N + M).

5.3. Iteration - Time O(N + M), Space O(1)

• Idea: Because it store in reverse order => You can calculate from left to right and get carry.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

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

        carry = 0
        while l1 or l2 or carry:
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0

            # new digit
            val = v1 + v2 + carry
            carry = val // 10
            val = val % 10
            cur.next = ListNode(val)

            # update ptrs
            cur = cur.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy.next

• Time: O(N + M).

• Space: O(1) extra space.

6. Dry run examples

l1 = [1 -> 2 -> 3]
l2 = [9]