Add Two Numbers II

Given two linked lists that represent two numbers, return the sum of the numbers also represented as a list.

Note: The digits are stored with the most significant digit first (normal order, not reversed).

Example(s)

Example 1:

Input: a = 1->2, b = 1->3
Output: 2->5
Explanation:
a represents 12, b represents 13
12 + 13 = 25
Result: 2->5

Example 2:

Input: a = 1->9, b = 1
Output: 2->0
Explanation:
a represents 19, b represents 1
19 + 1 = 20
Result: 2->0

Example 3:

Input: a = 7->2->4->3, b = 5->6->4
Output: 7->8->0->7
Explanation:
a represents 7243, b represents 564
7243 + 564 = 7807
Result: 7->8->0->7

Solution

The solution uses stacks to reverse the order:

Push to stacks: Push all digits from both lists onto stacks
Pop and add: Pop digits from stacks, add them with carry
Build result: Build result list in reverse order (least significant first)
Reverse result: Reverse the result list to get most significant first

JavaScript Solution
Python Solution

JavaScript Solution - Stack Approach

/**
* Definition for singly-linked list.
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/

/**
* Add two numbers represented as linked lists
* @param {ListNode} l1 - First number (most significant digit first)
* @param {ListNode} l2 - Second number (most significant digit first)
* @return {ListNode} - Sum as linked list (most significant digit first)
*/
function addTwoNumbers(l1, l2) {
// Step 1: Push digits to stacks
const stack1 = [];
const stack2 = [];

let current1 = l1;
while (current1) {
  stack1.push(current1.val);
  current1 = current1.next;
}

let current2 = l2;
while (current2) {
  stack2.push(current2.val);
  current2 = current2.next;
}

// Step 2: Pop from stacks and add
let carry = 0;
let result = null;

while (stack1.length > 0 || stack2.length > 0 || carry > 0) {
  const val1 = stack1.length > 0 ? stack1.pop() : 0;
  const val2 = stack2.length > 0 ? stack2.pop() : 0;
  
  const sum = val1 + val2 + carry;
  const digit = sum % 10;
  carry = Math.floor(sum / 10);
  
  // Create new node and add to front of result
  const newNode = new ListNode(digit);
  newNode.next = result;
  result = newNode;
}

return result;
}

// Helper function to create a list node
function ListNode(val, next) {
this.val = (val===undefined ? 0 : val);
this.next = (next===undefined ? null : next);
}

// Helper function to print list
function printList(head) {
const result = [];
while (head) {
  result.push(head.val);
  head = head.next;
}
return result.join('->');
}

// Test case 1: 1->2 + 1->3 = 2->5
const list1a = new ListNode(1);
list1a.next = new ListNode(2);
const list1b = new ListNode(1);
list1b.next = new ListNode(3);
console.log('Example 1:', printList(addTwoNumbers(list1a, list1b))); // 2->5

// Test case 2: 1->9 + 1 = 2->0
const list2a = new ListNode(1);
list2a.next = new ListNode(9);
const list2b = new ListNode(1);
console.log('Example 2:', printList(addTwoNumbers(list2a, list2b))); // 2->0

// Test case 3: 7->2->4->3 + 5->6->4 = 7->8->0->7
const list3a = new ListNode(7);
list3a.next = new ListNode(2);
list3a.next.next = new ListNode(4);
list3a.next.next.next = new ListNode(3);
const list3b = new ListNode(5);
list3b.next = new ListNode(6);
list3b.next.next = new ListNode(4);
console.log('Example 3:', printList(addTwoNumbers(list3a, list3b))); // 7->8->0->7

Output:

Click "Run Code" to execute the code and see the results.

Python Solution - Stack Approach

from typing import Optional

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

def add_two_numbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
  """
  Add two numbers represented as linked lists
  
  Args:
      l1: First number (most significant digit first)
      l2: Second number (most significant digit first)
      
  Returns:
      ListNode: Sum as linked list (most significant digit first)
  """
  # Step 1: Push digits to stacks
  stack1 = []
  stack2 = []
  
  current1 = l1
  while current1:
      stack1.append(current1.val)
      current1 = current1.next
  
  current2 = l2
  while current2:
      stack2.append(current2.val)
      current2 = current2.next
  
  # Step 2: Pop from stacks and add
  carry = 0
  result = None
  
  while stack1 or stack2 or carry:
      val1 = stack1.pop() if stack1 else 0
      val2 = stack2.pop() if stack2 else 0
      
      total = val1 + val2 + carry
      digit = total % 10
      carry = total // 10
      
      # Create new node and add to front of result
      new_node = ListNode(digit)
      new_node.next = result
      result = new_node
  
  return result

# Helper function to print list
def print_list(head: Optional[ListNode]) -> str:
  result = []
  while head:
      result.append(str(head.val))
      head = head.next
  return '->'.join(result)

# Test case 1: 1->2 + 1->3 = 2->5
list1a = ListNode(1)
list1a.next = ListNode(2)
list1b = ListNode(1)
list1b.next = ListNode(3)
print('Example 1:', print_list(add_two_numbers(list1a, list1b)))  # 2->5

# Test case 2: 1->9 + 1 = 2->0
list2a = ListNode(1)
list2a.next = ListNode(9)
list2b = ListNode(1)
print('Example 2:', print_list(add_two_numbers(list2a, list2b)))  # 2->0

# Test case 3: 7->2->4->3 + 5->6->4 = 7->8->0->7
list3a = ListNode(7)
list3a.next = ListNode(2)
list3a.next.next = ListNode(4)
list3a.next.next.next = ListNode(3)
list3b = ListNode(5)
list3b.next = ListNode(6)
list3b.next.next = ListNode(4)
print('Example 3:', print_list(add_two_numbers(list3a, list3b)))  # 7->8->0->7

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (Reverse Lists)

Here's an approach that reverses the lists, adds, then reverses the result:

JavaScript Reverse
Python Reverse

/**
 * Alternative: Reverse lists, add, reverse result
 */
function addTwoNumbersReverse(l1, l2) {
  // Reverse both lists
  l1 = reverseList(l1);
  l2 = reverseList(l2);
  
  // Add numbers (least significant first)
  let carry = 0;
  let dummy = new ListNode(0);
  let current = dummy;
  
  while (l1 || l2 || carry) {
    const val1 = l1 ? l1.val : 0;
    const val2 = l2 ? l2.val : 0;
    
    const sum = val1 + val2 + carry;
    const digit = sum % 10;
    carry = Math.floor(sum / 10);
    
    current.next = new ListNode(digit);
    current = current.next;
    
    if (l1) l1 = l1.next;
    if (l2) l2 = l2.next;
  }
  
  // Reverse result to get most significant first
  return reverseList(dummy.next);
}

function reverseList(head) {
  let prev = null;
  let current = head;
  
  while (current) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  
  return prev;
}

def add_two_numbers_reverse(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    """
    Alternative: Reverse lists, add, reverse result
    """
    # Reverse both lists
    l1 = reverse_list(l1)
    l2 = reverse_list(l2)
    
    # Add numbers (least significant first)
    carry = 0
    dummy = ListNode(0)
    current = dummy
    
    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        
        total = val1 + val2 + carry
        digit = total % 10
        carry = total // 10
        
        current.next = ListNode(digit)
        current = current.next
        
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next
    
    # Reverse result to get most significant first
    return reverse_list(dummy.next)

def reverse_list(head: Optional[ListNode]) -> Optional[ListNode]:
    prev = None
    current = head
    
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    
    return prev

Complexity

Time Complexity: O(max(m, n)) - Where m and n are the lengths of the two lists. We traverse each list once to push to stacks, then once to pop and add.
Space Complexity: O(m + n) - For the two stacks storing digits from both lists.

Approach

The solution uses stacks to reverse the order:

Push to stacks:
- Traverse both lists and push all digits onto separate stacks
- This reverses the order (most significant becomes top of stack)
Pop and add:
- Pop digits from both stacks
- Add corresponding digits along with carry
- Create result nodes (least significant first)
Build result:
- Add new nodes to the front of the result list
- This naturally reverses the order back to most significant first
Handle carry:
- If there's a carry after processing all digits, add one more node

Key Insights

Stacks reverse order: Push digits to reverse, pop to get in reverse order
Add from right: Process least significant digits first
Build from front: Adding nodes to front reverses the order
Carry propagation: Handle carry from right to left
Different lengths: Stacks handle lists of different lengths naturally

Step-by-Step Example

Let's trace through Example 1: a = 1->2, b = 1->3

Step 1: Push to stacks
  List a: 1->2
    Push 1 → stack1 = [1]
    Push 2 → stack1 = [1, 2]
  
  List b: 1->3
    Push 1 → stack2 = [1]
    Push 3 → stack2 = [1, 3]

Step 2: Pop and add
  Initial: result = null, carry = 0
  
  Iteration 1:
    Pop from stack1: val1 = 2
    Pop from stack2: val2 = 3
    sum = 2 + 3 + 0 = 5
    digit = 5, carry = 0
    result = 5->null
  
  Iteration 2:
    Pop from stack1: val1 = 1
    Pop from stack2: val2 = 1
    sum = 1 + 1 + 0 = 2
    digit = 2, carry = 0
    result = 2->5->null
  
  Iteration 3:
    Both stacks empty, carry = 0 → stop

Result: 2->5

Let's trace through Example 2: a = 1->9, b = 1

Step 1: Push to stacks
  stack1 = [1, 9]
  stack2 = [1]

Step 2: Pop and add
  Iteration 1:
    val1 = 9, val2 = 1
    sum = 9 + 1 + 0 = 10
    digit = 0, carry = 1
    result = 0->null
  
  Iteration 2:
    val1 = 1, val2 = 0 (stack2 empty)
    sum = 1 + 0 + 1 = 2
    digit = 2, carry = 0
    result = 2->0->null

Result: 2->0

Visual Representation

Example 1: 1->2 + 1->3 = 2->5

Lists:        Stacks:        Addition:
1->2         [1, 2]         2 + 3 = 5
1->3    →    [1, 3]    →    1 + 1 = 2
                            Result: 2->5

Example 2: 1->9 + 1 = 2->0

Lists:        Stacks:        Addition:
1->9         [1, 9]         9 + 1 = 10 (carry 1)
1       →    [1]       →    1 + 0 + 1 = 2
                            Result: 2->0

Edge Cases

Different lengths: Shorter list padded with zeros
Carry at end: Need to add one more node if carry remains
Both empty: Return null or 0
One empty: Return the other list
Large numbers: Works with any size (no integer overflow)

Important Notes

Most significant first: Digits stored in normal order (not reversed)
Stack approach: Efficiently reverses order without modifying input lists
Carry handling: Must handle carry from right to left
Different lengths: Stacks naturally handle this
No list modification: Stack approach doesn't modify input lists

Add Two Numbers: Similar but digits stored in reverse order
Multiply Strings: Different arithmetic operation
Reverse Linked List: Used in alternative approach
Plus One: Add one to number represented as array

Takeaways

Stacks efficiently reverse order for processing
Add from right (least significant first) is natural
Build from front reverses order back to most significant first
Carry propagation must be handled correctly
O(max(m,n)) time is optimal (must process all digits)

Example(s)​

Solution​

JavaScript Solution - Stack Approach

Output:

Python Solution - Stack Approach

Output:

Alternative Solution (Reverse Lists)​

Complexity​

Approach​

Key Insights​

Step-by-Step Example​

Visual Representation​

Edge Cases​

Important Notes​

Related Problems​

Takeaways​

Example(s)

Solution

Alternative Solution (Reverse Lists)

Complexity

Approach

Key Insights

Step-by-Step Example

Visual Representation

Edge Cases

Important Notes

Related Problems

Takeaways