Add Two Numbers (LeetCode 2)

The problem

Two non-negative integers are stored as linked lists, one digit per node, with the least significant digit first. Return their sum as a linked list in the same reversed format. Neither number has leading zeros, except the number 0 itself.

Input:  a = 2 -> 4 -> 3      (342)
        b = 5 -> 6 -> 4      (465)
Output: 7 -> 0 -> 8          (807)

342 + 465 = 807, and 807 written lowest digit first is 7 -> 0 -> 8.

How to think about it

Start with brute force. Turn each list into an integer, add them, and turn the sum back into a list. In Python that works because integers don’t overflow, but in Java or C++ a 100-digit list overflows any built-in type. Interviewers want the digit-level solution, and it’s simpler anyway.

The key insight: the reversed order is a gift. School addition starts at the units digit and moves left, carrying as it goes. The lists already start at the units digit, so you can walk both lists front to back in step, add the two digits plus the carry, write sum % 10 as the next node, and carry sum // 10 forward.

Lists of different lengths are fine. When one list runs out, treat its digit as 0. And don’t stop when both lists are empty if a carry is left: 99 + 1 needs a third digit. One loop condition, while a or b or carry, covers all three cases.

Which pattern is this? A linked-list parallel walk building a new list with a dummy head. The tell is “two lists, combine them node by node into a new list”.

Approach

1. Create a dummy node d, set tail = d and carry = 0.
2. While a has nodes, or b has nodes, or carry is non-zero:
   • s = carry + (a's digit or 0) + (b's digit or 0),
   • carry, digit = divmod(s, 10),
   • append a new node with digit and move tail to it,
   • advance a and b if they are not already None.
3. Return d.next.

Solution

class ListNode:                                   # LeetCode's node type
    def __init__(self, val=0, next=None):
        self.val = val; self.next = next

def add_two_numbers(a, b):
    d = ListNode(); tail = d; carry = 0
    while a or b or carry:                        # keep going while a final carry remains
        s = carry + (a.val if a else 0) + (b.val if b else 0)   # missing digit counts as 0
        carry, digit = divmod(s, 10)
        tail.next = ListNode(digit); tail = tail.next
        a = a.next if a else None; b = b.next if b else None
    return d.next
# add_two_numbers([2,4,3], [5,6,4]) -> [7,0,8]   (342 + 465 = 807)

Dry run

On a = 2 -> 4 -> 3, b = 5 -> 6 -> 4:

Both lists are empty and carry is 0, so the loop ends. Result: 7 -> 0 -> 8.

Complexity

• Time: O(max(m, n)). One iteration per digit of the longer number, plus at most one for a final carry.
• Space: O(1) extra. Only a few variables besides the output list. The output itself has max(m, n) + 1 nodes at most.

Edge cases and pitfalls

• Final carry: [9,9] + [1] must give [0,0,1]. Stopping when both lists end gives [0,0], which is wrong.
• Different lengths: the if a else 0 guards let the shorter list “run out” safely.
• Both numbers zero: [0] + [0] gives [0].
• Converting to int. Fine in Python, but it overflows in fixed-width languages and misses the point of the question.
• Forward-order variant (LeetCode 445). If digits are most significant first, reverse both lists first (or use stacks), then run this same loop.

Related problems

• Merge Two Sorted Lists (LeetCode 21): the same two-list walk with a dummy head and tail.
• Reverse Linked List (LeetCode 206): what you’d use first if the digits were stored the other way round.
• Plus One (LeetCode 66): the same carry logic on an array.