Sum linked lists as reversed integers

You're sitting across from your Apple interviewer when they pull up a blank editor and ask, "Given two numbers stored as reversed linked lists, can you add them together and return the result as a linked list?" This problem, also known as "Add Two Numbers" on other platforms like LeetCode and Blind 75, is one of the most frequently asked linked list questions in technical interviews. It shows up at Apple, Google, Meta, Amazon, and Bloomberg with remarkable consistency, and for good reason: it tests linked list traversal, pointer management, and arithmetic carry logic all in one clean package.

TL;DR

Traverse both linked lists simultaneously, adding corresponding digits along with any carry from the previous position. Use a dummy head node to simplify result list construction. At each step, compute sum = carry + digit1 + digit2, create a new node with sum % 10, and update carry to sum / 10. After both lists are exhausted, check for a remaining carry. This runs in O(n) time and O(n) space where n is the length of the longer list.

Prefer a different language? Jump to solutions in other languages.

Why This Problem Matters

Adding two numbers as linked lists bridges the gap between data structure manipulation and basic arithmetic. I've seen this problem used as the first "real" question after a warm-up in countless phone screens. It's approachable enough that most candidates can make progress, but the edge cases around carry propagation and mismatched list lengths separate solid engineers from the rest. Once you nail this pattern, you'll find it transferable to problems involving linked list merging, multi-precision arithmetic, and other node-by-node traversal tasks.

Understanding the Problem

You receive two singly linked lists, each representing a non-negative integer in reverse order. Each node holds a single digit (0-9). Your job is to add these two numbers and return the sum as a new linked list, also in reverse order.

The reversed storage is actually a gift. Think about how you add numbers by hand: you start from the rightmost digit (the ones place) and work left. Since the least significant digit is already at the head of each list, you can process nodes from head to tail and the digit order lines up perfectly with manual addition.

Here is the example: addTwoNumbers([2,4,3], [5,6,4]) returns [7,0,8].

List l1 represents the number 342 (digits reversed):

List l2 represents the number 465:

Result represents 342 + 465 = 807:

Edge Cases to Watch

1. Both lists are [0]: The result should be [0], not an empty list.
2. Different lengths: [1,8] + [0] should produce [1,8], treating the shorter list's missing digits as zeros.
3. Final carry: [9,9,9] + [1] produces [0,0,0,1], a result longer than either input.
4. One list much longer: [1,0,0,0,0,0,0,0,0] + [1] should correctly propagate through the longer list.

Solution Approach

The algorithm mirrors how you would add two numbers on paper, column by column from right to left. Since the lists are already reversed, "right to left" becomes "head to tail."

The Dummy Head Technique

A common linked list trick is to start with a dummy node at the front of the result list. This avoids writing separate logic for creating the first node versus appending to an existing list. Every new digit gets appended in the same way, and at the end you simply return dummyHead.next.

The highlighted node is the dummy. It never appears in the final result.

Walking Through the Algorithm

Let's trace addTwoNumbers([2,4,3], [5,6,4]) step by step:

Step 1: digits 2 and 5, carry 0. Sum = 2 + 5 + 0 = 7. New digit = 7, carry = 0.

Step 2: digits 4 and 6, carry 0. Sum = 4 + 6 + 0 = 10. New digit = 0, carry = 1.

Step 3: digits 3 and 4, carry 1. Sum = 3 + 4 + 1 = 8. New digit = 8, carry = 0.

Both lists are exhausted and carry is 0, so we're done. The result is [7, 0, 8], representing 807.

Here's the full state evolution across the algorithm:

Notice how the carry of 1 in step 2 feeds into step 3. This ripple effect is exactly what makes carry propagation the trickiest part of the problem.

Carry Propagation

The most subtle edge case is when a carry propagates beyond the length of both input lists. Consider adding 999 and 1:

The second list runs out after one node, but we keep going because the first list still has nodes. After all nodes are processed, carry is 1, so we append one more node:

Forgetting the final carry check is the single most common bug I see candidates introduce on this problem. Always check if (carry > 0) after the loop.

Implementation

public class Solution {
  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode current1 = l1, current2 = l2, currentResult = dummyHead;
    int carry = 0;

    while (current1 != null || current2 != null) {
      int digit1 = (current1 != null) ? current1.data : 0;
      int digit2 = (current2 != null) ? current2.data : 0;
      int sum = carry + digit1 + digit2;
      carry = sum / 10;
      currentResult.next = new ListNode(sum % 10);
      currentResult = currentResult.next;
      if (current1 != null) current1 = current1.next;
      if (current2 != null) current2 = current2.next;
    }

    if (carry > 0) {
      currentResult.next = new ListNode(carry);
    }

    return dummyHead.next;
  }
}

The loop condition current1 != null || current2 != null is the key. It keeps running as long as either list has remaining nodes. When one list is shorter, its pointer becomes null and we substitute 0 for its digit. This handles mismatched lengths without any special branching.

The carry logic is straightforward integer division: sum / 10 gives the carry (0 or 1 since the maximum sum of two digits plus a carry is 9 + 9 + 1 = 19), and sum % 10 gives the digit to store.

Complexity Analysis

Time Complexity: O(max(m, n))

We traverse both lists in a single pass. The loop runs for max(m, n) iterations where m and n are the lengths of the two lists. Each iteration does constant work: two null checks, one addition, one division, one modulo, and one node allocation.

Space Complexity: O(max(m, n))

The result list contains at most max(m, n) + 1 nodes (the extra node accounts for a potential final carry). We don't use any auxiliary data structures beyond the result list and a few pointer variables.

If the interviewer asks whether you can do this in O(1) extra space (excluding the output), the answer is yes by modifying one of the input lists in place. But that destroys the inputs, which is usually undesirable.

Common Pitfalls

1. Forgetting the final carry: After the loop, if carry is still 1, you need one more node. Missing this means [5] + [5] returns [0] instead of [0, 1].

2. Using && instead of || in the loop condition: With &&, the loop stops when the shorter list ends, leaving the remaining digits of the longer list unprocessed.

3. Not handling null pointers: When one list is shorter, you must check for null before accessing .data. The ternary (current1 != null) ? current1.data : 0 handles this cleanly.

4. Returning dummyHead instead of dummyHead.next: The dummy node is scaffolding. The actual result starts at the node after it.

Interview Tips

When this problem comes up in an interview:

1. Clarify the representation: Confirm that digits are stored in reverse order. Ask whether the numbers can have leading zeros (they shouldn't, except for the number 0 itself).

2. Mention the dummy head technique upfront: It shows you've worked with linked lists before and know how to simplify construction logic.

3. Walk through the carry example: Trace through a case like [9,9] + [1] to demonstrate you've thought about edge cases. This is the kind of thing that impresses interviewers.

4. Discuss the forward-order variant: If the interviewer asks "What if the digits were in forward order?", mention that you'd either reverse both lists first (O(n) extra pass) or use a stack-based approach. This shows breadth of thinking.

5. Know the recursive alternative: The Scala solution below uses recursion. Being able to discuss both iterative and recursive approaches shows flexibility.

Key Takeaways

• The dummy head pattern eliminates special-case logic for the first node and is reusable across many linked list construction problems.
• The || loop condition ensures you process all nodes from both lists, treating exhausted lists as contributing zero.
• Always check for a remaining carry after the loop. The result can be one node longer than the longer input.
• Reversed digit order aligns naturally with right-to-left addition, making this version simpler than the forward-order variant.
• Each digit sum is at most 19 (9 + 9 + 1), so the carry is always 0 or 1. No need for a more complex carry mechanism.

Related Problems

Once you're comfortable with this problem, try these to deepen your linked list skills:

• Reverse a linked list (the foundation for many linked list manipulations)
• Merge two sorted linked lists (similar simultaneous traversal pattern)
• Multiply two numbers represented as linked lists (extends the carry concept)
• Add two numbers stored in forward order (requires reversing or using stacks)

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews at top companies. Whether you're targeting Apple, Google, or your next dream role, consistent practice with problems like this builds the muscle memory that makes interview day feel routine.

Solutions in Other Languages

Python

class Solution:
    def add_two_numbers(self, l1, l2):
        dummy_head = ListNode(0)
        current_result = dummy_head
        carry = 0
        current1, current2 = l1, l2

        while current1 is not None or current2 is not None:
            digit1 = current1.data if current1 is not None else 0
            digit2 = current2.data if current2 is not None else 0
            total = carry + digit1 + digit2
            carry = total // 10
            current_result.next = ListNode(total % 10)
            current_result = current_result.next
            if current1 is not None:
                current1 = current1.next
            if current2 is not None:
                current2 = current2.next

        if carry > 0:
            current_result.next = ListNode(carry)

        return dummy_head.next

JavaScript

class Solution {
  addTwoNumbers(l1, l2) {
    let dummyHead = new ListNode(0);
    let currentResult = dummyHead;
    let carry = 0;
    let current1 = l1, current2 = l2;

    while (current1 !== null || current2 !== null) {
      let digit1 = (current1 !== null) ? current1.data : 0;
      let digit2 = (current2 !== null) ? current2.data : 0;
      let sum = carry + digit1 + digit2;
      carry = Math.floor(sum / 10);
      currentResult.next = new ListNode(sum % 10);
      currentResult = currentResult.next;
      if (current1 !== null) current1 = current1.next;
      if (current2 !== null) current2 = current2.next;
    }

    if (carry > 0) {
      currentResult.next = new ListNode(carry);
    }

    return dummyHead.next;
  }
}

TypeScript

class Solution {
  addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const dummyHead = new ListNode(0);
    let currentResult: ListNode = dummyHead;
    let carry = 0;
    let current1 = l1, current2 = l2;

    while (current1 !== null || current2 !== null) {
      const digit1 = (current1 !== null) ? current1.data : 0;
      const digit2 = (current2 !== null) ? current2.data : 0;
      const sum = carry + digit1 + digit2;
      carry = Math.floor(sum / 10);
      currentResult.next = new ListNode(sum % 10);
      currentResult = currentResult.next;
      if (current1 !== null) current1 = current1.next;
      if (current2 !== null) current2 = current2.next;
    }

    if (carry > 0) {
      currentResult.next = new ListNode(carry);
    }

    return dummyHead.next;
  }
}

C++

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* currentResult = dummyHead;
        int carry = 0;
        ListNode* current1 = l1;
        ListNode* current2 = l2;

        while (current1 != nullptr || current2 != nullptr) {
            int digit1 = (current1 != nullptr) ? current1->data : 0;
            int digit2 = (current2 != nullptr) ? current2->data : 0;
            int sum = carry + digit1 + digit2;
            carry = sum / 10;
            currentResult->next = new ListNode(sum % 10);
            currentResult = currentResult->next;
            if (current1 != nullptr) current1 = current1->next;
            if (current2 != nullptr) current2 = current2->next;
        }

        if (carry > 0) {
            currentResult->next = new ListNode(carry);
        }

        ListNode* result = dummyHead->next;
        delete dummyHead;
        return result;
    }
};

The C++ version includes manual memory management, freeing the dummy head node before returning.

Scala

The Scala solution takes a recursive approach, which is a natural fit for the language's functional style:

class Solution {
  def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
    def addLists(current1: ListNode, current2: ListNode, carry: Int): ListNode = {
      if (current1 == null && current2 == null && carry == 0) {
        null
      } else {
        val sum = (if (current1 != null) current1.data else 0) +
                  (if (current2 != null) current2.data else 0) + carry
        val resultNode = ListNode(sum % 10)
        resultNode.next = addLists(
          if (current1 != null) current1.next else null,
          if (current2 != null) current2.next else null,
          sum / 10
        )
        resultNode
      }
    }

    addLists(l1, l2, 0)
  }
}

The recursive version passes the carry as a parameter, and the base case handles the final carry check naturally: it only returns null when both lists are exhausted and carry is zero.

Kotlin

Kotlin uses its null-safe operators (?. and ?:) to handle null checks concisely:

class Solution {
  fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
    val dummyHead = ListNode(0)
    var current1 = l1
    var current2 = l2
    var currentResult = dummyHead
    var carry = 0

    while (current1 != null || current2 != null) {
      val digit1 = current1?.data ?: 0
      val digit2 = current2?.data ?: 0
      val sum = carry + digit1 + digit2
      carry = sum / 10
      currentResult.next = ListNode(sum % 10)
      currentResult = currentResult.next!!
      current1 = current1?.next
      current2 = current2?.next
    }

    if (carry > 0) {
      currentResult.next = ListNode(carry)
    }

    return dummyHead.next
  }
}

Swift

class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        let dummyHead = ListNode(0)
        var current1 = l1
        var current2 = l2
        var currentResult = dummyHead
        var carry = 0

        while current1 != nil || current2 != nil {
            let digit1 = current1?.data ?? 0
            let digit2 = current2?.data ?? 0
            let sum = carry + digit1 + digit2
            carry = sum / 10
            currentResult.next = ListNode(sum % 10)
            currentResult = currentResult.next!
            current1 = current1?.next
            current2 = current2?.next
        }

        if carry > 0 {
            currentResult.next = ListNode(carry)
        }

        return dummyHead.next
    }
}

Ruby

class Solution
  def add_two_numbers(l1, l2)
    dummy_head = ListNode.new(0)
    current1, current2, current_result = l1, l2, dummy_head
    carry = 0

    while !current1.nil? || !current2.nil?
      digit1 = current1.nil? ? 0 : current1.data
      digit2 = current2.nil? ? 0 : current2.data
      total = carry + digit1 + digit2
      carry = total / 10
      current_result.next = ListNode.new(total % 10)
      current_result = current_result.next
      current1 = current1.next unless current1.nil?
      current2 = current2.next unless current2.nil?
    end

    if carry > 0
      current_result.next = ListNode.new(carry)
    end

    dummy_head.next
  end
end

Rust

Rust's ownership model requires careful handling of borrowed references when traversing linked lists:

impl Solution {
    pub fn add_two_numbers(
        &self,
        l1: Option<Box<ListNode>>,
        l2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let mut dummy = Box::new(ListNode::new(0));
        let mut current1 = &l1;
        let mut current2 = &l2;
        let mut current_result = &mut dummy;
        let mut carry = 0;

        while current1.is_some() || current2.is_some() {
            let digit1 = current1.as_ref().map_or(0, |n| n.data);
            let digit2 = current2.as_ref().map_or(0, |n| n.data);
            let sum = carry + digit1 + digit2;
            carry = sum / 10;
            current_result.next = Some(Box::new(ListNode::new(sum % 10)));
            current_result = current_result.next.as_mut().unwrap();
            current1 = if let Some(ref n) = current1 { &n.next } else { current1 };
            current2 = if let Some(ref n) = current2 { &n.next } else { current2 };
        }

        if carry > 0 {
            current_result.next = Some(Box::new(ListNode::new(carry)));
        }

        dummy.next
    }
}

Dart

class Solution {
  ListNode? addTwoNumbers(ListNode? l1, ListNode? l2) {
    ListNode dummyHead = ListNode(0);
    ListNode? current1 = l1;
    ListNode? current2 = l2;
    ListNode currentResult = dummyHead;
    int carry = 0;

    while (current1 != null || current2 != null) {
      int digit1 = current1?.data ?? 0;
      int digit2 = current2?.data ?? 0;
      int sum = carry + digit1 + digit2;
      carry = sum ~/ 10;
      currentResult.next = ListNode(sum % 10);
      currentResult = currentResult.next!;
      current1 = current1?.next;
      current2 = current2?.next;
    }

    if (carry > 0) {
      currentResult.next = ListNode(carry);
    }

    return dummyHead.next;
  }
}

Note Dart's integer division operator ~/ instead of /.

PHP

class Solution {
    public function addTwoNumbers(?ListNode $l1, ?ListNode $l2): ?ListNode {
        $dummyHead = new ListNode(0);
        $current1 = $l1;
        $current2 = $l2;
        $currentResult = $dummyHead;
        $carry = 0;

        while ($current1 !== null || $current2 !== null) {
            $digit1 = ($current1 !== null) ? $current1->data : 0;
            $digit2 = ($current2 !== null) ? $current2->data : 0;
            $sum = $carry + $digit1 + $digit2;
            $carry = intdiv($sum, 10);
            $currentResult->next = new ListNode($sum % 10);
            $currentResult = $currentResult->next;
            if ($current1 !== null) $current1 = $current1->next;
            if ($current2 !== null) $current2 = $current2->next;
        }

        if ($carry > 0) {
            $currentResult->next = new ListNode($carry);
        }

        return $dummyHead->next;
    }
}

C#

public class Solution {
    public ListNode? AddTwoNumbers(ListNode? l1, ListNode? l2) {
        var dummyHead = new ListNode(0);
        ListNode? current1 = l1, current2 = l2;
        ListNode currentResult = dummyHead;
        int carry = 0;

        while (current1 != null || current2 != null) {
            int digit1 = (current1 != null) ? current1.data : 0;
            int digit2 = (current2 != null) ? current2.data : 0;
            int sum = carry + digit1 + digit2;
            carry = sum / 10;
            currentResult.next = new ListNode(sum % 10);
            currentResult = currentResult.next;
            if (current1 != null) current1 = current1.next;
            if (current2 != null) current2 = current2.next;
        }

        if (carry > 0) {
            currentResult.next = new ListNode(carry);
        }

        return dummyHead.next;
    }
}