Add Two Numbers — Solution

Problem

You have two linked lists where each node holds a single digit of a non-negative integer, stored least significant digit first. Add the two numbers together and return the result in the same reversed format.

Example — [2,4,3] + [5,6,4]:

[2,4,3]

[5,6,4]

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

Counter-example — lists of different length with a final carry:

[9,9]

[1]

• Input: l1 = [9,9], l2 = [1]
• Output: [0,0,1]
• Explanation: 99 + 1 = 100, stored reversed as [0,0,1]; forgetting the final carry here gives the wrong answer [0,0]

Intuition

Because the digits are stored in reverse order, the head of each list is already the ones place — exactly where elementary-school addition starts. Walk both lists in lockstep, sum the two digits plus any carry from the previous column, and emit the result digit. The tricky part is knowing when to stop: you must continue until both lists are exhausted and there is no remaining carry.

Solution — Iterative Digit Simulation

Traverse both lists simultaneously, computing the column sum at each position as digit_one + digit_two + carry. Append a new node with column_sum % 10 and propagate carry = column_sum // 10 to the next iteration. A dummy head node eliminates the special case of setting the result head.

1. Create a dummy_head node and a current pointer starting there; set carry = 0.
2. Loop while either list still has nodes or carry is non-zero.
3. Treat an exhausted list's contribution as 0 for this column.
4. Compute column_sum = digit_one + digit_two + carry.
5. Append a new node with value column_sum % 10; update carry = column_sum // 10.
6. Advance each non-null list pointer; return dummy_head.next.

1class Solution:
2    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
3        dummy_head = ListNode(0)
4        current = dummy_head
5        carry = 0
6
7        while l1 or l2 or carry:
8            digit_one = l1.val if l1 else 0  # treat exhausted list as contributing 0
9            digit_two = l2.val if l2 else 0
10
11            column_sum = digit_one + digit_two + carry
12            carry = column_sum // 10          # carry into the next column
13            current.next = ListNode(column_sum % 10)
14            current = current.next
15
16            if l1:
17                l1 = l1.next
18            if l2:
19                l2 = l2.next
20
21        return dummy_head.next

Time: O(max(m, n)) — every node in both lists is visited exactly once, and the result has at most max(m, n) + 1 nodes.

Space: O(max(m, n)) — the output list holds at most max(m, n) + 1 nodes; no extra auxiliary space beyond that.

Complexity Summary

Common Mistakes

• Using while l1 and l2 as the loop condition — this stops as soon as either list ends, silently discarding remaining digits from the longer list and any leftover carry.
• Forgetting to append a node for the final carry — if the last column sums to ≥ 10, carry = 1 remains after both lists are done; skipping it produces a result that is too short (e.g., 99 + 1 returns [0,0] instead of [0,0,1]).
• Reusing input list nodes for output — mutating l1.val or redirecting l1.next changes the caller's data; always allocate fresh ListNode objects for the result.
• Forgetting the dummy head — without it you need a special case to initialize the result head, and the logic for the first node differs from all subsequent nodes.
• Advancing both pointers unconditionally — calling l1 = l1.next when l1 is already None causes a null-pointer error; guard each advance with a null check.

Related Problems

• Merge Two Sorted Lists — same two-pointer linked-list traversal pattern, merging instead of summing
• Add Binary — identical carry-based digit addition applied to binary strings instead of linked lists
• Multiply Strings — extends column-by-column arithmetic to multi-digit multiplication on string representations
• Reverse Linked List — foundational linked list pointer manipulation; a prerequisite skill for this problem
• Palindrome Linked List — linked list traversal with careful pointer bookkeeping, same null-check discipline required