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 node contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not have leading zeros, except the number 0 itself.

Examples

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

Input:  l1 = [0], l2 = [0]
Output: [0]

Input:  l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints

• The number of nodes in each list is in the range [1, 100].
• 0 ≤ Node.val ≤ 9
• It is guaranteed that the list represents a number that does not have leading zeros.

Key Insight

Because digits are stored in reverse order (least-significant digit first), we can traverse both lists simultaneously from left to right, adding corresponding digits plus any carry, and append each result digit to the output list — no reversal needed.

1. Recursion O(max(m,n)) time · O(max(m,n)) space (call stack)

Intuition

Each recursive call handles one digit position. We extract v1 and v2 from the current nodes (or 0 if a list is exhausted), compute the digit and new carry, create the result node, then recurse with the tails and the new carry. The base case fires when both lists are null and carry is 0, returning null.

The visualization shows three rows: l1 (indigo) and l2 (amber) advance on the descent; the result (green) row is revealed right-to-left as the recursion unwinds. The pink carry badge shows the carry propagated downward.

• Descent: advance l1/l2 pointers, compute carry down the call stack.
• Base case: l1=None, l2=None, carry=0 → return None.
• Ascent: create Node(digit), set node.next to the previously returned node, return upward.

Time: O(max(m, n))  |  Space: O(max(m, n)) call stack

2. Iteration — Dummy Head O(max(m,n)) time · O(1) extra space

Intuition

Use a dummy head node so we never need a special case for the first node. A cur pointer starts at dummy and advances with each created node. We loop while either list has nodes or there is a carry remaining.

In the visualization: the cyan cur pointer shows where the last result node is; the pink carry badge shows the carry value; result nodes (green) build left-to-right as we iterate. The l1/l2 pointers advance and gray out exhausted nodes.

• Create dummy = ListNode(0), cur = dummy, carry = 0.
• Each iteration: read v1/v2 (0 if list exhausted), compute total, create cur.next = ListNode(total % 10), advance cur and both list pointers.
• After the loop, return dummy.next.

Time: O(max(m, n))  |  Space: O(1) extra (O(max(m,n)) output)

Common Pitfalls

• Forgetting the carry after the loop: if carry = 1 after both lists are exhausted (e.g. 999 + 1), you must still create one more node. The while l1 or l2 or carry condition handles this automatically.
• Unequal list lengths: one list can be longer than the other. Use v = node.val if node else 0 rather than assuming both nodes exist every iteration.
• Returning head vs dummy.next: the dummy node itself is not part of the result; always return dummy.next.
• Recursion stack depth: for very long lists (up to 100 nodes), recursion adds O(n) call stack overhead vs. O(1) for iteration. Both are accepted on LeetCode, but iteration is preferred in production.
• Leading zeros in input: the problem guarantees none (except the number 0), so you don't need to strip them.