1. Reverse List

Intuition

When adding two numbers, we naturally start from the least significant digit. The problem gives us numbers stored with the most significant digit first, so reversing both lists makes the addition straightforward.

After reversing, we can walk through both lists simultaneously, adding corresponding digits along with any carry. We build the result by prepending each new digit to our answer, which naturally produces the correct order without needing another reversal at the end.

Algorithm

1. Reverse both linked lists l1 and l2.
2. Initialize head = null and carry = 0.
3. While either list has nodes remaining or carry > 0:
   • Get the values v1 and v2 from the current nodes (use 0 if a list is exhausted).
   • Compute total = v1 + v2 + carry.
   • Create a new node with value total % 10 and prepend it to head.
   • Update carry = total / 10.
   • Advance both list pointers.
4. Return head.

# 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]:
        def reverseList(head):
            prev, curr = None, head
            while curr:
                temp = curr.next
                curr.next = prev
                prev = curr
                curr = temp
            return prev

        l1 = reverseList(l1)
        l2 = reverseList(l2)
        head = None
        carry = 0

        while l1 or l2 or carry:
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0
            total = v1 + v2 + carry
            carry = total // 10
            node = ListNode(total % 10)
            node.next = head
            head = node
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return head

Time & Space Complexity

• Time complexity: $O(m + n)$
• Space complexity: $O(max(m, n))$ for the output list.

Where $m$ is the length of $l1$ and $n$ is the length of $l2$.

---

2. Stack

Intuition

If we want to avoid modifying the input lists, we can use stacks to reverse the digit order implicitly. Pushing all digits onto stacks gives us access to them in reverse order when we pop.

This approach preserves the original lists while still allowing us to process digits from least significant to most significant. The rest of the logic is identical: add digits with carry and build the result by prepending nodes.

Algorithm

1. Push all values from l1 onto stack s1 and all values from l2 onto stack s2.
2. Initialize head = null and carry = 0.
3. While either stack is non-empty or carry > 0:
   • Pop values from s1 and s2 (use 0 if a stack is empty).
   • Compute total = v1 + v2 + carry.
   • Create a new node with value total % 10 and prepend it to head.
   • Update carry = total / 10.
4. Return head.

# 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]:
        s1, s2 = [], []

        while l1:
            s1.append(l1.val)
            l1 = l1.next

        while l2:
            s2.append(l2.val)
            l2 = l2.next

        carry = 0
        head = None

        while s1 or s2 or carry:
            v1 = s1.pop() if s1 else 0
            v2 = s2.pop() if s2 else 0
            total = v1 + v2 + carry
            carry = total // 10
            node = ListNode(total % 10)
            node.next = head
            head = node

        return head

Time & Space Complexity

• Time complexity: $O(m + n)$
• Space complexity: $O(m + n)$

Where $m$ is the length of $l1$ and $n$ is the length of $l2$.

---

Common Pitfalls

Adding Digits from Head Instead of Tail

Unlike the basic "Add Two Numbers" problem, the digits here are stored most-significant-digit first. Trying to add digits directly from the head without reversing or using a stack produces wrong results since you are adding the wrong place values together.

# Wrong: adding from head directly
while l1 and l2:
    total = l1.val + l2.val  # Misaligned place values

Forgetting to Handle Lists of Different Lengths

When lists have different lengths, the shorter list needs to be padded conceptually with leading zeros. Failing to align the lists properly before addition causes incorrect results.

# Wrong: assuming lists are same length
while l1 and l2:  # Stops early when one list ends
    # ...

Building Result in Wrong Order

After computing digits from least to most significant, the result must be constructed so that the most significant digit is at the head. Appending to the tail instead of prepending creates a reversed result.

# Wrong: appending to tail
result.next = ListNode(digit)  # Should prepend: node.next = head; head = node