Add Two Numbers (Linked List)
You are given two non-empty lists representing two non-negative integers. The digits are stored in reverse order (least-significant digit first), and each element is a single digit (0-9). Add the two numbers and return the sum as a digit list, also in reverse order.
Implement the function:
```python def add_two_numbers(l1, l2): ... ```
where l1 and l2 are lists of ints, and the return value is a list of ints (least-significant-first). You may assume the two numbers do not contain any leading zeros, except the number 0 itself.
Constraints: - The number of digits in each list is in the range $[1, 100]$. - $0 \leq \text{digit} \leq 9$ - The lists represent numbers without leading zeros.
Example
add_two_numbers([2, 4, 3], [5, 6, 4]) -> [7, 0, 8]
The lists represent $342$ and $465$ (read least-significant-first), and $342 + 465 = 807$, whose digits in reverse order are $[7, 0, 8]$.
Hints
- Think about how you add two numbers by hand, starting from the least significant digit. The reverse-order storage means the head of each list is already the ones place.
- Use a carry variable. At each step, the new digit is $(d_1 + d_2 + \text{carry}) \bmod 10$ and the new carry is $(d_1 + d_2 + \text{carry}) / 10$.
- Use a dummy head node to avoid special-casing the first node of the result. Loop while either list has nodes remaining or carry is nonzero.
Worked Solution
How to Think About It: This is elementary-school addition, digit by digit, starting from the ones place -- which is exactly how the lists are ordered. You walk both lists in lockstep, add corresponding digits plus any carry from the previous step, and append one digit of the result each step. The only subtlety is handling lists of different lengths and a final carry that extends the result by one digit.
Algorithm: Maintain a carry variable initialized to 0. At each step, sum the current digits from both lists (treating exhausted lists as contributing 0) plus the carry. The new digit is the sum modulo 10, the new carry is the sum divided by 10. Continue until both lists are exhausted and the carry is 0. The function takes two digit lists and returns a digit list (both least-significant-first) -- it does not use linked-list nodes.
Code: ```python def add_two_numbers(l1, l2): # l1, l2 are non-empty lists of single digits (0-9) representing # non-negative integers stored in REVERSE order (least significant first). # Return their sum as a digit list, also least-significant-first. result = [] carry = 0 i = 0 n = max(len(l1), len(l2)) while i < n or carry: d1 = l1[i] if i < len(l1) else 0 d2 = l2[i] if i < len(l2) else 0 total = d1 + d2 + carry result.append(total % 10) carry = total // 10 i += 1 return result ```
Complexity: Time $O(\max(m, n))$ where $m$ and $n$ are the lengths of the two lists. Space $O(\max(m, n))$ for the result list.
Optimization notes: - Reduce branching: Reading both values with a default of 0 when an index is out of range (as done here) gives a uniform loop body and reduces branch misprediction versus separate length checks. - Stack vs. heap allocation: In a lower-level language, a pre-allocated array or arena allocator instead of per-node allocation cuts overhead significantly.
Answer: Walk both lists simultaneously with carry propagation, appending total % 10 and carrying total // 10. Time $O(\max(m, n))$, space $O(\max(m, n))$.
Intuition
This problem is really just the grade-school addition algorithm implemented on a linked list. The reverse storage order is actually convenient -- it means you process digits from least significant to most significant, exactly as you would when adding by hand. The carry propagation is the only thing that couples one digit position to the next.
In practice, this pattern shows up whenever you need to process two streams of data element-by-element with some local state (the carry). The optimization discussion is relevant for low-latency systems where allocation overhead and branch misprediction matter -- on a trading system's hot path, the difference between heap-allocating each node vs. using a pre-allocated buffer can be the difference between making and missing a fill.