LeetCode 2: Add Two Numbers

Problem Restatement

We are given two non-empty linked lists.

Each linked list represents a non-negative integer.

The digits are stored in reverse order.

For example:

2 -> 4 -> 3

actually represents the number:

342

because the least significant digit comes first.

We need to add the two numbers together and return the result as a linked list in the same reversed format.

Each node contains exactly one digit.

Input and Output

The linked list node structure:

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

Examples

Input:

l1 = 2 -> 4 -> 3
l2 = 5 -> 6 -> 4

The first list represents:

342

The second list represents:

465

Their sum is:

342 + 465 = 807

Because the output must also be reversed, we return:

7 -> 0 -> 8

Another example:

l1 = 0
l2 = 0

Result:

0

Another example:

l1 = 9 -> 9 -> 9 -> 9
l2 = 1

This represents:

9999 + 1 = 10000

Result:

0 -> 0 -> 0 -> 0 -> 1

The final carry creates a new node.

First Thought: Convert Everything Into Integers

One possible idea:

1. Traverse the linked list.
2. Convert the digits into integers.
3. Add the integers.
4. Convert the result back into a linked list.

For small numbers, this works.

Example:

2 -> 4 -> 3

becomes:

342

Then:

342 + 465 = 807

Finally:

7 -> 0 -> 8

Problem With Integer Conversion

This approach has several issues.

The linked lists may become very large.

Some languages cannot safely store extremely large integers.

More importantly, the problem is designed to test linked list manipulation and digit-by-digit arithmetic.

We should solve the problem directly using the linked lists themselves.

Key Insight

This problem behaves exactly like elementary school addition.

When adding two numbers by hand:

1. Add the current digits.
2. Add the carry from the previous step.
3. Write down the current digit.
4. Carry the overflow into the next column.

Example:

  342
+ 465
-----
  807

Digit by digit:

2 + 5 = 7
4 + 6 = 10
3 + 4 + 1 = 8

The linked lists already store digits from least significant to most significant.

That means we can process them naturally from left to right.

Visual Walkthrough

Start:

l1: 2 -> 4 -> 3
l2: 5 -> 6 -> 4
carry = 0

First digits:

2 + 5 + 0 = 7

Write digit:

7

New carry:

0

Second digits:

4 + 6 + 0 = 10

Write digit:

0

Carry:

1

Third digits:

3 + 4 + 1 = 8

Write digit:

8

Carry:

0

Final result:

7 -> 0 -> 8

Algorithm

We maintain:

Loop while:

• l1 still exists
• or l2 still exists
• or carry is non-zero

For every step:

1. Read the current digit from l1
2. Read the current digit from l2
3. Add both digits and the carry
4. Compute:
   • new digit
   • new carry
5. Create a new node
6. Move forward

The important formulas are:

Current digit:

New carry:

Correctness

At every iteration, we process exactly one decimal position.

Suppose:

• x is the current digit from l1
• y is the current digit from l2
• carry is the overflow from the previous position

Then:

x + y + carry

represents the correct sum for the current decimal place.

The ones digit becomes the node value.

The tens digit becomes the carry for the next iteration.

This matches exactly how decimal addition works.

The loop continues until:

• both linked lists are exhausted
• and no carry remains

Therefore every digit of the final sum is constructed correctly.

Complexity

Where:

• n is the length of l1
• m is the length of l2

Implementation

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

class Solution:
    def addTwoNumbers(
        self,
        l1: ListNode,
        l2: ListNode
    ) -> ListNode:

        dummy = ListNode()
        current = dummy

        carry = 0

        while l1 or l2 or carry:
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0

            total = x + y + carry

            digit = total % 10
            carry = total // 10

            current.next = ListNode(digit)

            current = current.next

            if l1:
                l1 = l1.next

            if l2:
                l2 = l2.next

        return dummy.next

Code Explanation

We first create a dummy node:

dummy = ListNode()

This simplifies linked list construction.

Without a dummy node, we would need special handling for the first element.

current always points to the tail of the result list.

current = dummy

We maintain the carry:

carry = 0

Inside the loop:

x = l1.val if l1 else 0
y = l2.val if l2 else 0

If one list becomes shorter, we treat missing digits as 0.

Then:

total = x + y + carry

Extract the new digit:

digit = total % 10

Extract the carry:

carry = total // 10

Create the next node:

current.next = ListNode(digit)

Move forward:

current = current.next

Finally:

return dummy.next

We skip the dummy node and return the real head.

Testing

Helper functions:

def build_list(values):
    dummy = ListNode()
    current = dummy

    for v in values:
        current.next = ListNode(v)
        current = current.next

    return dummy.next

def to_list(node):
    result = []

    while node:
        result.append(node.val)
        node = node.next

    return result

Tests:

def run_tests():
    s = Solution()

    l1 = build_list([2, 4, 3])
    l2 = build_list([5, 6, 4])

    assert to_list(s.addTwoNumbers(l1, l2)) == [7, 0, 8]

    l1 = build_list([0])
    l2 = build_list([0])

    assert to_list(s.addTwoNumbers(l1, l2)) == [0]

    l1 = build_list([9, 9, 9, 9])
    l2 = build_list([1])

    assert to_list(s.addTwoNumbers(l1, l2)) == [0, 0, 0, 0, 1]

    l1 = build_list([1, 8])
    l2 = build_list([0])

    assert to_list(s.addTwoNumbers(l1, l2)) == [1, 8]

    print("all tests passed")

run_tests()