LeetCode 2 - Add Two Numbers

The problem gives us two non empty singly linked lists. Each linked list represents a non negative integer, but the digits are stored in reverse order. That means the head node contains the least significant digit.

leetcodemediumlinked-listmathrecursion

LeetCode Problem 2

Difficulty: 🟡 Medium
Topics: Linked List, Math, Recursion

Solution

Add Two Numbers

Problem Understanding

The problem gives us two non empty singly linked lists. Each linked list represents a non negative integer, but the digits are stored in reverse order.

That means the head node contains the least significant digit.

For example:

  • [2,4,3] represents the number 342
  • [5,6,4] represents the number 465

The task is to add the two numbers together and return the result as another linked list, also stored in reverse order.

The result for the example above is:

  • 342 + 465 = 807
  • Reverse order representation becomes [7,0,8]

The important detail is that we are not supposed to convert the linked lists into actual integer values directly. While Python can handle very large integers, other languages may not, and the intended solution focuses on linked list manipulation and digit by digit addition.

The constraints tell us:

  • Each list has between 1 and 100 nodes
  • Each node contains a digit from 0 to 9
  • No leading zeros exist, except for the number 0

The input size is relatively small, but the problem is designed to test linked list traversal and carry propagation logic.

Several edge cases matter here:

  • Lists of different lengths, such as [1,8] and [0]
  • Carry propagation across multiple digits, such as [9,9,9] + [1]
  • Final carry after processing all nodes, such as 999 + 1 = 1000
  • Inputs containing only zero
  • One list ending earlier than the other

A naive implementation often fails when one list is shorter or when an extra carry remains after the final digit.

Approaches

Brute Force Approach

A straightforward approach is to reconstruct the two integers from the linked lists, add them together, then build a new linked list from the result.

The process works like this:

  1. Traverse the first linked list and compute the integer value.
  2. Traverse the second linked list and compute the integer value.
  3. Add the two integers.
  4. Convert the resulting sum back into a reversed linked list.

This approach is correct because it directly performs the arithmetic operation the problem asks for.

However, it has drawbacks:

  • It depends on integer conversion.
  • In some languages, the numbers could exceed built in integer limits.
  • It ignores the linked list nature of the problem.
  • It performs unnecessary number reconstruction.

Even though the constraints here are small enough that overflow is not a practical issue in Python, this is not considered the intended solution.

Optimal Approach

The better approach is to simulate elementary school addition digit by digit.

Since the digits are already stored in reverse order, we can process the linked lists from head to tail exactly the same way we add numbers manually from right to left.

At every step:

  • Add the current digits from both lists
  • Add any carry from the previous step
  • Store the ones digit in the result list
  • Carry the tens digit forward

This works naturally with linked lists and avoids reconstructing large integers entirely.

The key observation is that reverse order storage perfectly aligns with how addition normally proceeds.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n + m) O(max(n, m)) Converts linked lists into integers, then reconstructs result
Optimal O(max(n, m)) O(max(n, m)) Adds digits directly while traversing lists

Algorithm Walkthrough

  1. Create a dummy head node for the result list.

A dummy node simplifies linked list construction because we always append new nodes after it. This avoids special handling for the first node. 2. Initialize a pointer called current.

This pointer tracks the last node in the result list so new digits can be appended efficiently. 3. Initialize carry = 0.

Carry stores overflow from the previous digit addition. 4. Traverse both linked lists simultaneously.

Continue while at least one list still has nodes or a carry still exists. 5. Extract the current digit values.

If a list still has nodes, use its digit value. Otherwise use 0.

This handles lists of unequal length naturally. 6. Compute the digit sum.

Add:

  • value from first list
  • value from second list
  • carry from previous step
  1. Update carry.

Use integer division:

carry = total // 10

This keeps only the overflow portion. 8. Create the current result digit.

Use modulo:

digit = total % 10

This extracts the current digit to store. 9. Append a new node to the result list.

Create a node with the computed digit and attach it after current. 10. Advance all pointers.

Move:

  • current
  • l1
  • l2
  1. Return the real head.

Since the dummy node is artificial, return dummy.next.

Why it works

At every iteration, the algorithm correctly computes one digit of the final sum using the same carry based addition used in standard arithmetic.

Because the linked lists are stored in reverse order, the least significant digits appear first, allowing direct left to right traversal without reversing anything.

The invariant is:

  • Before each iteration, the result list already contains the correct sum for all previously processed digits.
  • The carry value correctly represents overflow into the next digit position.

When traversal ends, all digits and remaining carry have been processed, so the constructed linked list is the complete correct sum.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import Optional

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

        dummy = ListNode(0)
        current = dummy

        carry = 0

        while l1 or l2 or carry:

            value1 = l1.val if l1 else 0
            value2 = l2.val if l2 else 0

            total = value1 + value2 + carry

            carry = total // 10
            digit = total % 10

            current.next = ListNode(digit)
            current = current.next

            if l1:
                l1 = l1.next

            if l2:
                l2 = l2.next

        return dummy.next

The implementation starts by creating a dummy head node. This node acts as a stable starting point for the result linked list.

The current pointer always refers to the tail of the result list. Every newly computed digit gets appended after it.

The loop continues while there are still digits remaining in either list or a carry still needs processing. This condition is critical because a final carry may create an additional node.

Inside the loop, missing digits are treated as zero when one list becomes shorter than the other. This keeps the addition logic uniform.

The sum is split into two parts:

  • digit, which becomes the current node value
  • carry, which propagates into the next iteration

Finally, the function returns dummy.next because the dummy node itself is not part of the answer.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {

    dummy := &ListNode{}
    current := dummy

    carry := 0

    for l1 != nil || l2 != nil || carry != 0 {

        value1 := 0
        value2 := 0

        if l1 != nil {
            value1 = l1.Val
        }

        if l2 != nil {
            value2 = l2.Val
        }

        total := value1 + value2 + carry

        carry = total / 10
        digit := total % 10

        current.Next = &ListNode{Val: digit}
        current = current.Next

        if l1 != nil {
            l1 = l1.Next
        }

        if l2 != nil {
            l2 = l2.Next
        }
    }

    return dummy.Next
}

The Go solution follows the same logic as the Python implementation.

The main language specific difference is pointer handling. Go uses nil instead of None, and linked list nodes are created using struct pointers.

Integer overflow is not a concern because every intermediate calculation stays within a very small range. The maximum digit sum is:

9 + 9 + 1 = 19

So standard integer arithmetic is completely safe.

Worked Examples

Example 1

Input:

l1 = [2,4,3]
l2 = [5,6,4]

These represent:

342 + 465
Step value1 value2 carry before total digit carry after Result List
1 2 5 0 7 7 0 [7]
2 4 6 0 10 0 1 [7,0]
3 3 4 1 8 8 0 [7,0,8]

Final output:

[7,0,8]

Example 2

Input:

l1 = [0]
l2 = [0]
Step value1 value2 carry before total digit carry after Result List
1 0 0 0 0 0 0 [0]

Final output:

[0]

Example 3

Input:

l1 = [9,9,9,9,9,9,9]
l2 = [9,9,9,9]

These represent:

9999999 + 9999
Step value1 value2 carry before total digit carry after Result List
1 9 9 0 18 8 1 [8]
2 9 9 1 19 9 1 [8,9]
3 9 9 1 19 9 1 [8,9,9]
4 9 9 1 19 9 1 [8,9,9,9]
5 9 0 1 10 0 1 [8,9,9,9,0]
6 9 0 1 10 0 1 [8,9,9,9,0,0]
7 9 0 1 10 0 1 [8,9,9,9,0,0,0]
8 0 0 1 1 1 0 [8,9,9,9,0,0,0,1]

Final output:

[8,9,9,9,0,0,0,1]

Complexity Analysis

Measure Complexity Explanation
Time O(max(n, m)) Each node from both linked lists is visited once
Space O(max(n, m)) The output linked list stores the result digits

The algorithm processes each node exactly once, so the running time grows linearly with the longer input list.

The auxiliary working memory is technically O(1), because only a few variables are maintained. However, the returned linked list itself requires space proportional to the number of digits in the result.

Test Cases

# Helper functions

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

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

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

    return dummy.next

def to_list(node):
    result = []

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

    return result

solution = Solution()

# Example 1
l1 = build_list([2, 4, 3])
l2 = build_list([5, 6, 4])
assert to_list(solution.addTwoNumbers(l1, l2)) == [7, 0, 8]  # basic addition

# Example 2
l1 = build_list([0])
l2 = build_list([0])
assert to_list(solution.addTwoNumbers(l1, l2)) == [0]  # both zero

# Example 3
l1 = build_list([9, 9, 9, 9, 9, 9, 9])
l2 = build_list([9, 9, 9, 9])
assert to_list(solution.addTwoNumbers(l1, l2)) == [8, 9, 9, 9, 0, 0, 0, 1]  # cascading carry

# Different lengths
l1 = build_list([1, 8])
l2 = build_list([0])
assert to_list(solution.addTwoNumbers(l1, l2)) == [1, 8]  # shorter second list

# Final carry creation
l1 = build_list([9])
l2 = build_list([1])
assert to_list(solution.addTwoNumbers(l1, l2)) == [0, 1]  # extra node from carry

# Multiple carry propagation
l1 = build_list([9, 9, 9])
l2 = build_list([1])
assert to_list(solution.addTwoNumbers(l1, l2)) == [0, 0, 0, 1]  # carry through entire list

# No carry at all
l1 = build_list([1, 2, 3])
l2 = build_list([4, 5, 6])
assert to_list(solution.addTwoNumbers(l1, l2)) == [5, 7, 9]  # simple digit sums

# One list much longer
l1 = build_list([1])
l2 = build_list([9, 9, 9, 9, 9])
assert to_list(solution.addTwoNumbers(l1, l2)) == [0, 0, 0, 0, 0, 1]  # long carry chain

Test Case Summary

Test Why
[2,4,3] + [5,6,4] Standard addition case
[0] + [0] Smallest valid inputs
[9,9,9,9,9,9,9] + [9,9,9,9] Carry propagation across many digits
[1,8] + [0] Different list lengths
[9] + [1] Final carry creates new node
[9,9,9] + [1] Carry chain across entire list
[1,2,3] + [4,5,6] No carry anywhere
[1] + [9,9,9,9,9] One list significantly longer

Edge Cases

Both Inputs Are Zero

The simplest valid input is:

[0] + [0]

A buggy implementation might accidentally return an empty list if it assumes zero digits should be skipped.

This implementation correctly creates a node with value 0 because the loop processes the digits normally even when the sum is zero.

Final Carry After Traversal

Cases like:

[9] + [1]

produce:

[0,1]

The most common mistake is stopping traversal immediately after both lists end, ignoring the remaining carry.

This implementation avoids that problem by continuing the loop while carry is non zero:

while l1 or l2 or carry:

That extra iteration creates the final node correctly.

Lists With Different Lengths

Inputs such as:

[1,8] + [0]

can break implementations that assume both lists always have nodes available simultaneously.

This solution handles missing nodes by treating them as zero:

value1 = l1.val if l1 else 0
value2 = l2.val if l2 else 0

That allows addition to continue correctly even after one list finishes earlier than the other.