2. Add Two Numbers

Convert both linked lists to integers, add them, then convert the sum back to a linked list.

Brute Force

Traverse each list to extract its digits, reconstruct the integer (using the reverse-order representation), add the two integers, then convert the result back to a linked list digit by digit.

This works correctly but requires extracting the full number, which can overflow for very large inputs in some languages (Python handles big integers natively, but Java/C++ would fail for 100-digit numbers).

Time is O(n + m) where n and m are the list lengths. Space is O(max(n, m)) for the output.

Why it's not ideal: while it works in Python, it conceptually misses the point of the digit-by-digit approach and fails in languages with fixed-width integers.

import java.math.BigInteger;

class Solution {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        BigInteger num1 = toNumber(l1);
        BigInteger num2 = toNumber(l2);
        BigInteger total = num1.add(num2);

        if (total.equals(BigInteger.ZERO)) {
            return new ListNode(0);
        }

        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        while (total.compareTo(BigInteger.ZERO) > 0) {
            BigInteger[] divMod = total.divideAndRemainder(BigInteger.TEN);
            current.next = new ListNode(divMod[1].intValue());
            current = current.next;
            total = divMod[0];
        }
        return dummy.next;
    }

    private BigInteger toNumber(ListNode node) {
        BigInteger result = BigInteger.ZERO;
        BigInteger power = BigInteger.ONE;
        while (node != null) {
            result = result.add(BigInteger.valueOf(node.val).multiply(power));
            power = power.multiply(BigInteger.TEN);
            node = node.next;
        }
        return result;
    }
}

Walk both lists simultaneously, adding corresponding digits plus any carry from the previous step, just like pencil-and-paper addition.

Mental Model

Think of adding two numbers by hand, column by column from right to left. Since the linked lists are already in reverse order (least significant digit first), we can just walk forward through both lists and add digits naturally. If the sum of two digits exceeds 9, we carry 1 to the next column.

Algorithm Steps

1. Initialize a dummy head node and a current pointer. Set carry = 0.
2. While l1 is not None OR l2 is not None OR carry > 0: a. Get x = l1.val if l1 exists, else 0. b. Get y = l2.val if l2 exists, else 0. c. Compute total = x + y + carry. d. Set carry = total // 10 and digit = total % 10. e. Create a new node with value digit and attach it to current.next. f. Advance current, l1 (if exists), and l2 (if exists).
3. Return dummy.next.

Worked Walk-through

Example: l1 = [2,4,3] (342), l2 = [5,6,4] (465)

Result: [7,0,8] which represents 807 = 342 + 465.

Edge Cases

• Different lengths: l1 = [1], l2 = [9,9]. After l1 runs out, treat its digit as 0. Result: [0,0,1].
• Final carry: l1 = [5], l2 = [5]. Sum = 10, so we need an extra node: [0,1].
• One list is [0]: l1 = [0], l2 = [1,2,3]. Result is just [1,2,3].

Complexity

• Time: O(max(n, m)) — we walk the longer list once, plus at most one extra step for carry.
• Space: O(max(n, m)) — the result list has at most max(n, m) + 1 nodes.