Medium

Add Two Numbers

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.

Problem Statement

The problem is to add two non-empty linked lists representing two non-negative integers. The digits of each integer are stored in reverse order in the linked lists, where each node of the linked lists contains a single digit. The task is to calculate the sum of the two integers and return the result as a linked list with the digits of the sum also stored in reverse order. It can be assumed that the two numbers do not contain any leading zero, except the number 0 itself.

Examples

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Clarifying Questions

Are the linked lists of equal length or can they be of different lengths?
Are the digits stored in the linked lists in reverse order (least significant digit first)?
Are there any restrictions on the length of the linked lists?
Can we assume that the input linked lists are non-empty?
Are the digits in each node guaranteed to be single-digit non-negative integers (0-9)?
Can we assume that the output linked list should also be in reverse order (least significant digit first)?
Are there any other special cases or constraints that I should be aware of?

Solutions

There are different approaches to solving this problem. Here are a few common ones:

Iterate through both linked lists and add the corresponding digits, keeping track of any carryover, and building a new linked list with the resulting sum.
Convert the linked lists to integers, add them, and then convert the resulting sum back into a linked list.
Use recursion to traverse the linked lists and perform the addition, and create a new linked list with the resulting sum.
Reverse the linked lists, perform the addition, and then reverse the resulting linked list back to the original order.

Each of these approaches has its advantages and disadvantages, and the best approach depends on the specific requirements and constraints of the problem, as well as the preferences and experience of the developer.

Approach 1: Iterating through linked lists

Iterate through both linked lists and add the corresponding digits, keeping track of any carryover, and building a new linked list with the resulting sum.

Algorithm:

Initialize a new empty linked list.
Traverse the two input linked lists in parallel, starting from the head nodes, until both have reached the end of the list.
At each step, add the corresponding digits of the two linked lists, along with any carryover from the previous addition.
If the resulting sum is greater than 9, set the carryover to 1 and add the least significant digit of the sum to the new linked list.
If the resulting sum is less than or equal to 9, set the carryover to 0 and add the sum to the new linked list.
If one of the linked lists has more digits than the other, continue to add the digits of the longer linked list to the carryover until there are no more digits left.
If there is a carryover remaining at the end of the traversal, add it as an additional digit to the new linked list.
Return the resulting linked list.



public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = null;  // Initialize the result linked list to null
ListNode current = null;  // Initialize the current node to null
int carry = 0;  // Initialize the carry value to 0

// While either of the input linked lists is not null or there is a carry value
while (l1 != null || l2 != null) {
    int x = l1 != null ? l1.val : 0;  // Get the value of node from l1, if null set to 0
    int y = l2 != null ? l2.val : 0;  // Get the value of node from l2, if null set to 0
    int sum = x + y + carry;  // Add the values and the carry
    
    carry = sum / 10;  // Calculate the carry for next step
    sum = sum % 10;  // Calculate the value to add to the result linked list
    
    // Create a new node and add it to the result linked list
    if (result == null) {
        result = new ListNode(sum);
        current = result;
    } else {
        current.next = new ListNode(sum);
        current = current.next;
    }
    
    // Move to the next node in the linked lists
    if (l1 != null) l1 = l1.next;
    if (l2 != null) l2 = l2.next;
}

// If there is still a carry, add it as a new node to the result linked list
if (carry != 0) {
    current.next = new ListNode(carry);
}

return result;  // Return the result linked list
}




def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
result = None  # Initialize the result linked list to None
current = None  # Initialize the current node to None
carry = 0  # Initialize the carry value to 0

# While either of the input linked lists is not None or there is a carry value
while l1 is not None or l2 is not None or carry != 0:
x = l1.val if l1 is not None else 0  # Get the value of node from l1, if None set to 0
y = l2.val if l2 is not None else 0  # Get the value of node from l2, if None set to 0
s = x + y + carry  # Add the values and the carry

carry = s // 10  # Calculate the carry for next step
s = s % 10  # Calculate the value to add to the result linked list

# Create a new node and add it to the result linked list
if result is None:
result = ListNode(s)
current = result
else:
current.next = ListNode(s)
current = current.next

# Move to the next node in the linked lists
if l1 is not None:
l1 = l1.next
if l2 is not None:
l2 = l2.next

return result  # Return the result linked list




public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = null;  // Initialize the result linked list to null
ListNode current = null;  // Initialize the current node to null
int carry = 0;  // Initialize the carry value to 0

// While either of the input linked lists is not null or there is a carry value
while (l1 != null || l2 != null || carry != 0) {
int x = (l1 != null) ? l1.val : 0;  // Get the value of node from l1, if null set to 0
int y = (l2 != null) ? l2.val : 0;  // Get the value of node from l2, if null set to 0
int sum = x + y + carry;  // Add the values and the carry

carry = sum / 10;  // Calculate the carry for next step
sum = sum % 10;  // Calculate the value to add to the result linked list

// Create a new node and add it to the result linked list
if (result == null) {
result = new ListNode(sum);
current = result;
} else {
current.next = new ListNode(sum);
current = current.next;
}

// Move to the next node in the linked lists
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}

return result;  // Return the result linked list
}


ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* result = nullptr;  // Initialize the result linked list to null
ListNode* current = nullptr;  // Initialize the current node to null
int carry = 0;  // Initialize the carry value to 0

// While either of the input linked lists is not null or there is a carry value
while (l1 != nullptr || l2 != nullptr || carry != 0) {
int x = (l1 != nullptr) ? l1->val : 0;  // Get the value of node from l1, if null set to 0
int y = (l2 != nullptr) ? l2->val : 0;  // Get the value of node from l2, if null set to 0
int sum = x + y + carry;  // Add the values and the carry

carry = sum / 10;  // Calculate the carry for next step
sum = sum % 10;  // Calculate the value to add to the result linked list

// Create a new node and add it to the result linked list
if (result == nullptr) {
result = new ListNode(sum);
current = result;
} else {
current->next = new ListNode(sum);
current = current->next;
}

// Move to the next node in the linked lists
if (l1 != nullptr) {
l1 = l1->next;
}
if (l2 != nullptr) {
l2 = l2->next;
}
}

return result;  // Return the result linked list
}

Time complexity: O(max(m, n)), where m and n are the lengths of the input linked lists

Space complexity: O(max(m, n)), the length of the result linked list

Approach 2: Converting linked lists to integers

Convert the linked lists to integers, add them, and then convert the resulting sum back into a linked list.

Algorithm:

Traverse each input linked list in reverse order, starting from the tail node, and convert each linked list into an integer using the reversed digit order.
Add the two resulting integers.
Traverse the resulting integer digits in reverse order and create a new linked list with each digit as a node in the linked list.
Return the resulting linked list.


public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
int x = ListToInt(l1);  // Convert linked list l1 to integer x
int y = ListToInt(l2);  // Convert linked list l2 to integer y
int sum = x + y;  // Add x and y to get the sum

return IntToList(sum);  // Convert sum to a linked list and return it
}

// Helper method to convert linked list to integer
private int ListToInt(ListNode node) {
int result = 0;  // Initialize the result to 0
int multiplier = 1;  // Initialize the multiplier to 1

// Traverse the linked list, multiplying each digit by its place value
while (node != null) {
    result += node.val * multiplier;
    multiplier *= 10;
    node = node.next;
}

return result;  // Return the integer value of the linked list
}

// Helper method to convert integer to linked list
private ListNode IntToList(int num) {
if (num == 0) return new ListNode(0);  // Handle the edge case of sum being 0

ListNode result = null;  // Initialize the result linked list to null
ListNode current = null;  // Initialize the current node to null

// Convert the integer to a linked list, one digit at a time
while (num != 0) {
    int digit = num % 10;  // Get the last digit of the number
    
    // Create a new node and
    // add it to the result linked list
    if (result == null) {
        result = new ListNode(digit);
        current = result;
    } else {
        current.next = new ListNode(digit);
        current = current.next;
    }
    
    num /= 10;  // Remove the last digit from the number
}

return result;  // Return the result linked list
}



def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
x = self.listToInt(l1)  # Convert linked list l1 to integer x
y = self.listToInt(l2)  # Convert linked list l2 to integer y
s = x + y  # Add x and y to get the sum

return self.intToList(s)  # Convert sum to a linked list and return it

# Helper method to convert linked list to integer
def listToInt(self, node: ListNode) -> int:
result = 0  # Initialize the result to 0
multiplier = 1  # Initialize the multiplier to 1

# Traverse the linked list, multiplying each digit by its place value
while node is not None:
result += node.val * multiplier
multiplier *= 10
node = node.next

return result  # Return the integer value of the linked list

# Helper method to convert integer to linked list
def intToList(self, num: int) -> ListNode:
if num == 0:
return ListNode(0)  # Handle the edge case of sum being 0

result = None  # Initialize the result linked list to None
current = None  # Initialize the current node to None

# Convert the integer to a linked list, one digit at a time
while num != 0:
digit = num % 10  # Get the last digit of the number

# Create a new node and add it to
# the result linked list
if result is None:
    result = ListNode(digit)
    current = result
else:
    current.next = ListNode(digit)
    current = current.next

num //= 10  # Remove the last digit from the number

return result  # Return the result linked list


public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int x = listToInt(l1);  // Convert linked list l1 to integer x
int y = listToInt(l2);  // Convert linked list l2 to integer y
int sum = x + y;  // Add x and y to get the sum

return intToList(sum);  // Convert sum to a linked list and return it
}

// Helper method to convert linked list to integer
public int listToInt(ListNode node) {
int result = 0;  // Initialize the result to 0
int multiplier = 1;  // Initialize the multiplier to 1

// Traverse the linked list, multiplying each digit by its place value
while (node != null) {
    result += node.val * multiplier;
    multiplier *= 10;
    node = node.next;
}

return result;  // Return the integer value of the linked list
}

// Helper method to convert integer to linked list
public ListNode intToList(int num) {
if (num == 0) {
    return new ListNode(0);  // Handle the edge case of sum being 0
}

ListNode result = null;  // Initialize the result linked list to null
ListNode current = null;  // Initialize the current node to null

// Convert the integer to a linked list, one digit at a time
while (num != 0) {
    int digit
    = num % 10;  // Get the last digit of the number
    if (result == null) {
        result = new ListNode(digit);
        current = result;
    } else {
        current.next = new ListNode(digit);
        current = current.next;
    }
    num /= 10;  // Remove the last digit from the number
}

return result;  // Return the result linked list
}



ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int x = listToInt(l1);  // Convert linked list l1 to integer x
int y = listToInt(l2);  // Convert linked list l2 to integer y
int sum = x + y;  // Add x and y to get the sum

return intToList(sum);  // Convert sum to a linked list and return it
}

// Helper method to convert linked list to integer
int listToInt(ListNode* node) {
int result = 0;  // Initialize the result to 0
int multiplier = 1;  // Initialize the multiplier to 1

// Traverse the linked list, multiplying each digit by its place value
while (node != nullptr) {
    result += node->val * multiplier;
    multiplier *= 10;
    node = node->next;
}

return result;  // Return the integer value of the linked list
}

// Helper method to convert integer to linked list
ListNode* intToList(int num) {
if (num == 0) {
    return new ListNode(0);  // Handle the edge case of sum being 0
}

ListNode* result = nullptr;  // Initialize the result linked list to null
ListNode* current =
= nullptr;  // Initialize the current node to null

// Traverse the integer in reverse order, adding each digit to the linked list
while (num > 0) {
int digit = num % 10;  // Get the last digit of the number
if (result == nullptr) {
result = new ListNode(digit);
current = result;
} else {
current->next = new ListNode(digit);
current = current->next;
}
num /= 10;  // Remove the last digit from the number
}

return result;  // Return the result linked list
}

Time complexity: O(max(m, n)), where m and n are the lengths of the input linked lists

Space complexity: O(max(m, n)), the maximum recursion depth

Approach 3: Recursion

Use recursion to traverse the linked lists and perform the addition, and create a new linked list with the resulting sum.

Algorithm:

Initialize a new empty linked list.
Start with the head nodes of both input linked lists.
Define a recursive function that takes in two nodes as input, representing the current digits being added, and a carryover value.
In the recursive function, add the current digit values of the two nodes, along with the carryover value.
If the resulting sum is greater than 9, set the carryover to 1 and create a new node in the resulting linked list with the least significant digit of the sum.
If the resulting sum is less than or equal to 9, set the carryover to 0 and create a new node in the resulting linked list with the sum as the value.
If either of the input nodes is null, set the value of that node to 0 and continue with the addition.
Recursively call the function with the next nodes in each linked list and the new carryover value.
Return the resulting linked list.


public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
return AddTwoNumbersHelper(l1, l2, 0);
}

private ListNode AddTwoNumbersHelper(ListNode l1, ListNode l2, int carry) {
if (l1 == null && l2 == null && carry == 0) {
    return null;  // Base case: both lists and carry are empty, so return null
}

int val1 = (l1 != null) ? l1.val : 0;
int val2 = (l2 != null) ? l2.val : 0;

int sum = val1 + val2 + carry;  // Calculate the sum of the current digits and the carry

ListNode result = new ListNode(sum % 10);  // Create a new node for the current digit

// Recursively add the next digits, passing the new carry value to the next call
result.next = AddTwoNumbersHelper((l1 != null) ? l1.next : null, 
                                   (l2 != null) ? l2.next : null, 
                                   sum / 10);

return result;  // Return the resulting linked list
}


def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
return self.addTwoNumbersHelper(l1, l2, 0)

def addTwoNumbersHelper(self, l1: ListNode, l2: ListNode, carry: int) -> ListNode:
if not l1 and not l2 and carry == 0:
return None  # Base case: both lists and carry are empty, so return null

val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0

total = val1 + val2 + carry  # Calculate the sum of the current digits and the carry

result = ListNode(total % 10)  # Create a new node for the current digit

# Recursively add the next digits, passing the new carry value to the next call
result.next = self.addTwoNumbersHelper(l1.next if l1 else None, 
                                    l2.next if l2 else None, 
                                    total // 10)

return result  # Return the resulting linked list


public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
return addTwoNumbersHelper(l1, l2, 0);
}

private ListNode addTwoNumbersHelper(ListNode l1, ListNode l2, int carry) {
if (l1 == null && l2 == null && carry == 0) {
    return null;  // Base case: both lists and carry are empty, so return null
}
    
int val1 = (l1 != null) ? l1.val : 0;
int val2 = (l2 != null) ? l2.val : 0;
    
int sum = val1 + val2 + carry;  // Calculate the sum of the current digits and the carry
    
ListNode result = new ListNode(sum % 10);  // Create a new node for the current digit
    
// Recursively add the next digits, passing the new carry value to the next call
result.next = addTwoNumbersHelper((l1 != null) ? l1.next : null, 
                                    (l2 != null) ? l2.next : null, 
                                    sum / 10);
    
return result;  // Return the resulting linked list
}



ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
return addTwoNumbersHelper(l1, l2, 0);
}

ListNode* addTwoNumbersHelper(ListNode* l1, ListNode* l2, int carry) {
if (l1 == nullptr && l2 == nullptr && carry == 0) {
    return nullptr;  // Base case: both lists and carry are empty, so return null
}

int val1 = (l1 != nullptr) ? l1->val : 0;
int val2 = (l2 != nullptr) ? l2->val : 0;

int sum = val1 + val2 + carry;  // Calculate the sum of the current digits and the carry

ListNode* result = new ListNode(sum % 10);  // Create a new node for the current digit

// Recursively add the next digits, passing the new carry value to the next call
result->next = addTwoNumbersHelper((l1 != nullptr) ? l1->next : nullptr, 
                                     (l2 != nullptr) ? l2->next : nullptr, 
                                     sum / 10);

return result;  // Return the resulting linked list
}

Time complexity: O(max(m, n)), where m and n are the lengths of the input linked lists

Space complexity: O(max(m, n)), the length of the result linked list

Approach 4: Reversing the linked list

Reverse the linked lists, perform the addition, and then reverse the resulting linked list back to the original order.

Algorithm:

Reverse both input linked lists by reversing the order of nodes in each list.
Follow the algorithm for approach 1, iterating through both linked lists in parallel, adding corresponding digits, and keeping track of carryover to build a new linked list with the resulting sum.
Reverse the resulting linked list to restore the original order of digits.
Return the resulting linked list.



public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
ListNode l1Reversed = ReverseLinkedList(l1); // Reverse the first linked list
ListNode l2Reversed = ReverseLinkedList(l2); // Reverse the second linked list

ListNode result = new ListNode(0); // Create a dummy head for the result linked list
ListNode curr = result; // Create a reference to the dummy head

int carry = 0; // Initialize carry to 0

while (l1Reversed != null || l2Reversed != null) {
    int x = (l1Reversed != null) ? l1Reversed.val : 0;
    int y = (l2Reversed != null) ? l2Reversed.val : 0;
    
    int sum = x + y + carry;
    carry = sum / 10;
    curr.next = new ListNode(sum % 10);
    curr = curr.next;
    
    if (l1Reversed != null) l1Reversed = l1Reversed.next;
    if (l2Reversed != null) l2Reversed = l2Reversed.next;
}

if (carry > 0) {
    curr.next = new ListNode(carry); // Add the carry as a new node if it exists
}

return ReverseLinkedList(result.next); // Reverse the result linked list and return it
}

public ListNode ReverseLinkedList(ListNode head) {
ListNode prev = null;

while (head != null) {
    ListNode next = head.next;
    head.next = prev;
    prev = head;
    head = next;
}

return prev;
}



class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
l1_reversed = self.reverseLinkedList(l1) # Reverse the first linked list
l2_reversed = self.reverseLinkedList(l2) # Reverse the second linked list

result = ListNode(0) # Create a dummy head for the result linked list
curr = result # Create a reference to the dummy head

carry = 0 # Initialize carry to 0

while l1_reversed or l2_reversed:
    x = l1_reversed.val if l1_reversed else 0
    y = l2_reversed.val if l2_reversed else 0
    
    _sum = x + y + carry
    carry = _sum // 10
    curr.next = ListNode(_sum % 10)
    curr = curr.next
    
    if l1_reversed: l1_reversed = l1_reversed.next
    if l2_reversed: l2_reversed = l2_reversed.next

if carry:
    curr.next = ListNode(carry) # Add the carry as a new node if it exists

return self.reverseLinkedList(result.next) # Reverse the result linked list and return it

def reverseLinkedList(self, head: ListNode) -> ListNode:
prev = None

while head:
    next_node = head.next
    head.next = prev
    prev = head
    head = next_node

return prev



class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode l1Reversed = reverseLinkedList(l1); // Reverse the first linked list
    ListNode l2Reversed = reverseLinkedList(l2); // Reverse the second linked list
    
    ListNode result = new ListNode(0); // Create a dummy head for the result linked list
    ListNode curr = result; // Create a reference to the dummy head
    
    int carry = 0; // Initialize carry to 0
    
    while (l1Reversed != null || l2Reversed != null) {
        int x = (l1Reversed != null) ? l1Reversed.val : 0;
        int y = (l2Reversed != null) ? l2Reversed.val : 0;
        
        int sum = x + y + carry;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        
        if (l1Reversed != null) l1Reversed = l1Reversed.next;
        if (l2Reversed != null) l2Reversed = l2Reversed.next;
    }
    
    if (carry > 0) {
        curr.next = new ListNode(carry); // Add the carry as a new node if it exists
    }
    
    return reverseLinkedList(result.next); // Reverse the result linked list and return it
}

public ListNode reverseLinkedList(ListNode head) {
    ListNode prev = null;
    
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    
    return prev;
}
}



class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* l1Reversed = reverseLinkedList(l1); // Reverse the first linked list
ListNode* l2Reversed = reverseLinkedList(l2); // Reverse the second linked list

ListNode* result = new ListNode(0); // Create a dummy head for the result linked list
ListNode* curr = result; // Create a reference to the dummy head

int carry = 0; // Initialize carry to 0

while (l1Reversed != nullptr || l2Reversed != nullptr) {
int x = (l1Reversed != nullptr) ? l1Reversed->val : 0;
int y = (l2Reversed != nullptr) ? l2Reversed->val : 0;

int sum = x + y + carry;
carry = sum / 10;
curr->next = new ListNode(sum % 10);
curr = curr->next;

if (l1Reversed != nullptr) l1Reversed = l1Reversed->next;
if (l2Reversed != nullptr) l2Reversed = l2Reversed->next;
}

if (carry > 0) {
curr->next = new ListNode(carry); // Add the carry as a new node if it exists
}

return reverseLinkedList(result->next); // Reverse the result linked list and return it
}

ListNode* reverseLinkedList(ListNode* head) {
ListNode* prev = nullptr;

while (head != nullptr) {
ListNode* next = head->next;
head->next = prev;
prev = head;
head = next;
}

return prev;
}
};

Time complexity: O(max(m, n)), where m and n are the lengths of the input linked lists

Space complexity: O(max(m, n)), the length of the result linked list

All four approaches have the same time and space complexity of O(max(m, n)), where m and n are the lengths of the input linked lists. Therefore, all four approaches have the same asymptotic time and space complexity, and none of them is more optimal than the others in terms of Big O notation.

However, in practice, there may be some differences in performance due to the specific implementation details and the underlying hardware. For example, the recursive approach (Approach 3) may have slightly slower performance due to the overhead of the recursive function calls. The other two approaches (Approach 1 and Approach 2) are likely to have similar performance characteristics, but may differ in their implementation details.

Ultimately, the choice of which approach to use will depend on factors such as the specific requirements of the use case, the programming language and libraries being used, and any performance benchmarks or constraints that need to be met.

Updated: Oct 30, 2023

« Max Consecutive Ones

Find Numbers with Even Number of Digits »