Add Two Numbers

Table of Contents +

Add Two Numbers tests one quiet thing. Can you handle the carry cleanly? It is the same addition you learned as a kid, but done on linked lists. The trick is keeping your loop simple while one extra digit may spill over each step.

🎯 The Problem

You get two numbers stored as linked lists and add them.

  • A linked list is a chain of nodes where each node points to the next.
  • Each node holds one digit.
  • The digits are stored in reverse order, so the first node is the ones place.
  • Return the sum as a new linked list, also in reverse order.
  • Example: 2 -> 4 -> 3 means 342. 5 -> 6 -> 4 means 465. The sum 807 becomes 7 -> 0 -> 8.
Input:  l1 = 2 -> 4 -> 3   (means 342)
        l2 = 5 -> 6 -> 4   (means 465)
Output: 7 -> 0 -> 8        (means 807)


Explanation: 342 + 465 = 807

Here are the two input chains drawn as nodes and arrows.

2

4

3

5

6

4

🐢 Approach 1: Convert To A Number (Brute Force)

Rebuild both numbers, add them, then split the sum into digits.

The idea:

  • Read each list and rebuild the full number.
  • Add the two numbers normally.
  • Split the sum back into digits and build a new list.

Why it is weak:

  • These numbers can be very long, with hundreds of digits.
  • A normal integer cannot hold a number that big, so the value overflows.
  • It breaks on large inputs, and interviewers love large inputs.

Here is the conversion code:

add_two_numbers_conversion.py
def add_two_numbers(l1, l2):
    def to_number(node):
        place = 1
        total = 0
        while node:
            total += node.val * place
            place *= 10
            node = node.next
        return total


    value = to_number(l1) + to_number(l2)
    dummy = ListNode(0)
    cur = dummy
    for ch in str(value)[::-1]:
        cur.next = ListNode(int(ch))
        cur = cur.next
    return dummy.next

⚡ Approach 2: Add Digit By Digit With A Carry (Best)

The idea in one line: add one column at a time, exactly like addition on paper.

The idea:

  • Never build the whole number.
  • Start at the ones place, the front of each list, and move along together.
  • Add three things each step: this digit from list one, this digit from list two, and the carry.

How it works:

  • The carry is the extra ten that spills into the next column. 7 + 5 is 12, so write 2 and carry 1.
  • Store the digit sum % 10. Set the new carry to sum / 10.
  • Make a new node for the digit and attach it. Move both lists forward.
  • A missing digit counts as zero, so lists of different lengths just work.

How it finishes:

  • Loop while either list has nodes or a carry is still waiting.
  • If a carry remains at the end, add one more node for it.
  • A dummy node is a fake node before the real head. It removes the special case for the first attachment. Return dummy.next.

Here is the column-by-column addition for the example.

2+5=7 carry 0

4+6=10 write 0 carry 1

3+4+1=8 carry 0

Result: 7 0 8

Steps to Solve

  1. Make a dummy node and a current pointer that starts at the dummy. Set carry to zero.
  2. Loop while either list has a node, or while the carry is not zero.
  3. Take the digit from each list, using zero if that list has ended.
  4. Add the two digits and the carry to get a sum.
  5. Store sum % 10 in a new node, and set the carry to sum / 10.
  6. Attach the new node, then move current and both list pointers forward.
  7. Return dummy.next as the head of the answer list.

This Python version uses a small Node class and a dummy node so the first attachment needs no special case.

add_two_numbers.py
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None




def add_two_numbers(l1, l2):
    dummy = Node(0)              # fake node before the real head
    current = dummy
    carry = 0
    while l1 or l2 or carry:
        x = l1.val if l1 else 0  # missing digit counts as 0
        y = l2.val if l2 else 0
        total = x + y + carry
        carry = total // 10      # tens spill into next column
        current.next = Node(total % 10)
        current = current.next
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next
    return dummy.next




def print_list(head):
    parts = []
    cur = head
    while cur:
        parts.append(str(cur.val))
        cur = cur.next
    print(" -> ".join(parts))




l1 = Node(2)
l1.next = Node(4)
l1.next.next = Node(3)
l2 = Node(5)
l2.next = Node(6)
l2.next.next = Node(4)
result = add_two_numbers(l1, l2)
print_list(result)

The output of the above code will be:

7 -> 0 -> 8

Let us walk through the Python version line by line and see why each part is there.

The line dummy = Node(0) makes the fake starting node. We never read its value. We just need something to attach the first real node to. The line current = dummy points at where the next node will go.

The line while l1 or l2 or carry is the heart of it. We keep looping while either list still has digits, or while a carry is still waiting to be placed. So even if both lists end, a leftover carry adds one final node.

The lines x = l1.val if l1 else 0 and y = l2.val if l2 else 0 read the current digits. If a list has ended, its digit counts as zero. That single rule handles lists of different lengths without any special code.

The line total = x + y + carry adds the column. Then carry = total // 10 keeps the tens part for the next column. The // is integer division, which throws away the remainder. And total % 10 is the remainder, which is the digit we store right now.

The lines current.next = Node(total % 10) and current = current.next attach the new digit and move forward. The last two if checks step each list forward only if it still has a node. At the end we return dummy.next, which is the real first digit of the answer.

⏱️ Time and Space Complexity

We touch each digit of both lists once. So the time is O(n), where n is the length of the longer list. We also build a new list of about the same length to hold the answer. So the extra space is also O(n). The convert-to-number way looks shorter but breaks on big numbers, so it is not a real option.

Approach Time Complexity Space Complexity
Convert to number then add O(n) O(n) and overflows on big inputs
Digit by digit with carry O(n) O(n)

Tip

The two things people forget are the final carry and the different lengths. Always loop while a carry remains, and always treat a missing digit as zero. Those two habits cover almost every edge case in this problem.

🧩 Key Takeaways

  • ✅ Add one column at a time, just like addition on paper, starting from the ones place.
  • ✅ Track the carry and keep looping while a carry still waits.
  • ✅ Treat a missing digit as zero so lists of different lengths just work.
  • ✅ A dummy node removes the special case for attaching the first node.
  • ✅ Never rebuild the whole number, because big lists overflow normal integers.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    In what order are the digits stored in each linked list?

    Why: Digits are stored in reverse, so 342 is stored as 2 -> 4 -> 3, with the ones place first.

  2. 2

    What is the carry after adding the digits 7 and 5?

    Why: 7 + 5 = 12. You write down 2 (which is 12 % 10) and carry 1 (which is 12 / 10) into the next column.

  3. 3

    Why does the loop also continue while the carry is not zero?

    Why: If both lists end but a carry remains, that carry still needs its own node, so the loop must keep going.

  4. 4

    What does the dummy node do in this solution?

    Why: The dummy node gives a fixed starting point, so attaching the first real node needs no special code. We return dummy.next.

Score: 0 / 4

🚀 What’s Next?

Previous Reorder List Next Copy List with Random Pointer