Add Two Numbers

Difficulty: Medium Source: NeetCode

Problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes 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.

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

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

Example 3: 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 linked 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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Linked List Traversal — walking two lists simultaneously
• Carry Arithmetic — how digit-by-digit addition with carry works (like doing addition by hand)
• Dummy Head Trick — building a result list cleanly

1. Simulate Addition (Optimal)

Intuition

The lists are already in reverse order — least significant digit first — which is exactly how we do long addition by hand: start from the least significant digit, add, carry the overflow. So we just simulate this process directly on the linked lists.

Walk both lists simultaneously, add corresponding digits plus any carry from the previous step. The sum at each position can be 0–19 (9+9+1 carry), so the digit is total % 10 and the new carry is total // 10. Continue until both lists are exhausted and there’s no remaining carry.

l1 = 2 -> 4 -> 3   (represents 342)
l2 = 5 -> 6 -> 4   (represents 465)

Position 0:  2 + 5 + carry(0) = 7,  digit=7, carry=0
Position 1:  4 + 6 + carry(0) = 10, digit=0, carry=1
Position 2:  3 + 4 + carry(1) = 8,  digit=8, carry=0
Both exhausted, carry=0, done.

Result: 7 -> 0 -> 8  (represents 807)

Algorithm

1. Create a dummy head and a cur pointer.
2. Initialize carry = 0.
3. While l1 or l2 or carry is non-zero:
   • Get digits: v1 = l1.val if l1 else 0, v2 = l2.val if l2 else 0.
   • Compute total = v1 + v2 + carry.
   • New digit: total % 10. New carry: total // 10.
   • Append a new node with the digit to the result.
   • Advance l1 and l2 if they’re not exhausted.
4. Return dummy.next.

Solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    cur = head
    for v in values[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    return head

def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result) if result else "None")

def addTwoNumbers(l1, l2):
    dummy = ListNode(0)
    cur = dummy
    carry = 0

    while l1 or l2 or carry:
        v1 = l1.val if l1 else 0
        v2 = l2.val if l2 else 0

        total = v1 + v2 + carry
        carry = total // 10
        digit = total % 10

        cur.next = ListNode(digit)
        cur = cur.next

        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next

    return dummy.next

# Test cases
l1 = build_list([2, 4, 3])  # 342
l2 = build_list([5, 6, 4])  # 465
print("Output: ", end=""); print_list(addTwoNumbers(l1, l2))  # 7->0->8 (807)

l3 = build_list([0])
l4 = build_list([0])
print("Output: ", end=""); print_list(addTwoNumbers(l3, l4))  # 0

l5 = build_list([9, 9, 9, 9, 9, 9, 9])  # 9999999
l6 = build_list([9, 9, 9, 9])            # 9999
print("Output: ", end=""); print_list(addTwoNumbers(l5, l6))  # 8->9->9->9->0->0->0->1

# Lists of different lengths
l7 = build_list([1])
l8 = build_list([9, 9])  # 99 + 1 = 100
print("Output: ", end=""); print_list(addTwoNumbers(l7, l8))  # 0->0->1

# Final carry creates new node
l9 = build_list([5])
l10 = build_list([5])  # 5 + 5 = 10
print("Output: ", end=""); print_list(addTwoNumbers(l9, l10))  # 0->1

Complexity

• Time: O(max(m, n)) — we iterate as many times as the longer list (plus possibly one extra for a final carry)
• Space: O(max(m, n)) — the result list has at most max(m, n) + 1 nodes

2. Convert to Integer and Back (Brute Force)

Intuition

Since the lists are in reverse order, we can read each list as a number, add them as regular Python integers, then convert the result back to a linked list. Python handles arbitrarily large integers, so there’s no overflow concern. This is simple but misses the point of the problem (and wouldn’t work in languages with fixed-size integers).

Algorithm

1. Walk l1 and reconstruct the integer (least significant digit at index 0 means multiply by 10^i).
2. Same for l2.
3. Compute total = num1 + num2.
4. Build the result list from total by repeatedly taking total % 10 and appending.

Solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    cur = head
    for v in values[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    return head

def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result) if result else "None")

def addTwoNumbers_brute(l1, l2):
    def list_to_int(node):
        num, multiplier = 0, 1
        while node:
            num += node.val * multiplier
            multiplier *= 10
            node = node.next
        return num

    total = list_to_int(l1) + list_to_int(l2)

    if total == 0:
        return ListNode(0)

    dummy = ListNode(0)
    cur = dummy
    while total > 0:
        cur.next = ListNode(total % 10)
        cur = cur.next
        total //= 10
    return dummy.next

# Test
l1 = build_list([2, 4, 3])
l2 = build_list([5, 6, 4])
print("Output: ", end=""); print_list(addTwoNumbers_brute(l1, l2))  # 7->0->8

Complexity

• Time: O(max(m, n)) — similar traversal
• Space: O(max(m, n)) — result list

Common Pitfalls

Forgetting the final carry. After both lists are exhausted, there may still be a carry of 1 (e.g., 5+5=10 leaves carry=1). The while l1 or l2 or carry condition handles this — don’t change it to just while l1 or l2.

Not handling lists of different lengths. If l1 has 3 nodes and l2 has 2, you need to keep going after l2 is exhausted. Use v1 = l1.val if l1 else 0 to safely get 0 when a list runs out.

Advancing both pointers unconditionally. After the loop body, only advance a pointer if it’s not None. if l1: l1 = l1.next — don’t do l1 = l1.next unconditionally or you’ll get an AttributeError.