Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Leetcode 2. Add Two Numbers

Asked at:

DESCRIPTION

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 contain any leading zero, except the number 0 itself.

Input:

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

Output:

[7,0,8]

Explanation: 342 + 465 = 807. The lists represent these numbers in reverse: 2->4->3 is 342, 5->6->4 is 465, and the result 7->0->8 is 807

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

Understanding the Problem

Let's understand what we're being asked to do. We have two linked lists representing numbers in reverse order. For example, the number 342 would be stored as 2 -> 4 -> 3.

If we're adding 342 + 465, the linked lists would be 2 -> 4 -> 3 and 5 -> 6 -> 4. We need to return the sum 807 as 7 -> 0 -> 8.

Let's trace through step-by-step: Start at the heads. Add 2 + 5 = 7 (first digit). Then 4 + 6 = 10 (second digit - we have a carry of 1!). Then 3 + 4 + 1 (carry) = 8 (third digit). Result: 7 -> 0 -> 8.

Important constraint: The digits are stored in reverse order, which actually makes addition easier since we naturally add from right to left (least significant digit first).

Edge cases to consider: What if the lists have different lengths? What if there's a carry at the end (like 99 + 1 = 100)? What if one or both lists are empty?

Building Intuition

When adding numbers by hand, we start from the rightmost digit (least significant) and move left, carrying over when a sum exceeds 9.

Since the linked lists store digits in reverse order, the head of each list is already the least significant digit! This means we can traverse both lists from head to tail, adding corresponding digits and tracking the carry.

The reverse storage eliminates the need to reverse the lists or use extra space to store digits. We can build the result list as we go, adding each sum digit as a new node.

The carry mechanism is crucial: when digit1 + digit2 + carry >= 10, we store (sum % 10) in the current node and pass carry = 1 to the next addition.

Think about how you'd add 342 + 465 on paper:

  342
+ 465
-----

You'd compute: 2+5=7, then 4+6=10 (write 0, carry 1), then 3+4+1=8. Final answer: 807.

With reversed linked lists 2->4->3 and 5->6->4, we're doing the exact same process but traversing forward through the lists instead of backward through the digits!

Common Mistakes

Forgetting to handle the final carry after both lists are exhausted - if carry is 1 at the end, you need to add a new node with value 1

Not handling lists of different lengths correctly - treat missing nodes as having value 0, don't assume lists are equal length

Creating the result list incorrectly - need a dummy head node to simplify insertion, and remember to return dummy.next, not dummy

Integer overflow when computing sum - while unlikely with single digits, always use (val1 + val2 + carry) % 10 for the digit and (val1 + val2 + carry) / 10 for carry

Modifying the input lists instead of creating a new result list - the problem asks for a new linked list, not in-place modification

Optimal Solution

Traverse both linked lists simultaneously from head to tail, adding corresponding digits along with any carry from the previous addition. Create a new node for each digit of the result. Handle cases where lists have different lengths by treating missing nodes as 0. After processing both lists, if there's a remaining carry, add one final node with value 1. This approach processes each digit exactly once while building the result list.

Visualization

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def add_two_numbers(l1, l2):
    """
    Add two numbers represented as linked lists in reverse order.
    Returns the sum as a new linked list.
    """
    # Create dummy head for result list
    dummy_head = ListNode(0)
    current = dummy_head
    carry = 0
    
    # Traverse both lists simultaneously
    while l1 is not None or l2 is not None or carry != 0:
        # Get values from current nodes (0 if node is None)
        val1 = l1.val if l1 is not None else 0
        val2 = l2.val if l2 is not None else 0
        
        # Calculate sum and new carry
        total = val1 + val2 + carry
        carry = total // 10
        digit = total % 10
        
        # Create new node with digit
        current.next = ListNode(digit)
        current = current.next
        
        # Move to next nodes if they exist
        if l1 is not None:
            l1 = l1.next
        if l2 is not None:
            l2 = l2.next
    
    # Return the result list (skip dummy head)
    return dummy_head.next

Start adding two numbers represented as linked lists

0 / 17

Test Your Knowledge

Complexity Analysis

Time Complexity: O(max(m, n)) We traverse both lists once, where m and n are the lengths of the two lists. We process max(m,n) digits total

Space Complexity: O(max(m, n)) The result list will have at most max(m,n) + 1 nodes (the extra node is for a potential final carry)

What We've Learned

Linked list traversal with simultaneous iteration: When processing two linked lists in parallel, use a single loop with null-safe checks (`while l1 or l2`) rather than nested loops - this elegantly handles lists of different lengths without extra complexity.
Carry propagation pattern: In digit-by-digit arithmetic operations, maintain a carry variable that persists across iterations, adding it to each position's sum and updating it with integer division (`carry = total // 10`) - this mirrors how manual addition works column by column.
Dummy head node technique: Create a dummy node before your result list's head to avoid special-casing the first insertion - this eliminates conditional logic for empty list initialization and simplifies returning `dummy.next` as the final result.
Post-loop carry handling: The most common bug is forgetting to check if carry remains after both lists are exhausted - always add a final node if `carry > 0` after the main loop to handle cases like 999 + 1 = 1000.
In-place construction optimization: Build the result list on-the-fly during traversal rather than storing values in an array first - this achieves O(1) space complexity (excluding output) and O(max(m,n)) time, processing each digit exactly once.
Reverse-order storage insight: This problem exploits least-significant-digit-first storage which naturally aligns with how carry propagates in addition (right-to-left) - recognize that reversed representations can simplify arithmetic operations on linked lists compared to normal order.

Test Your Understanding

Why is linked-list the right data structure for this problem?

linked-list provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Late October, 2025

Oracle

Senior

Late October, 2025

Oracle

Senior

Was expecting to finish the question in 20mins with variations of the question. So timing matters.

Mid October, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 2. Add Two Numbers

DESCRIPTION

Understanding the Problem

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact