We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Add Two Numbers II

Difficulty: Medium

Problem Description

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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.

Key Insights

  • The linked lists represent numbers in reverse order, with the most significant digit at the head.
  • We can use a stack to reverse the order of the digits while maintaining the addition logic.
  • The addition can be performed digit by digit, taking care of the carry for values exceeding 9.
  • The final result should also be constructed in the correct order, which can be done using another stack.

Space and Time Complexity

Time Complexity: O(n + m), where n and m are the lengths of the two linked lists. Space Complexity: O(n + m), for storing the digits in stacks.

Solution

To solve the problem, we can use two stacks to hold the digits of the two numbers represented by the linked lists. By pushing each digit onto its respective stack, we can then pop the digits from the stacks to perform the addition starting from the least significant digit. We maintain a carry variable to handle sums that exceed 9. Finally, we construct the resulting linked list in the correct order by iterating through the results saved in another stack.

Code Solutions

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

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    stack1, stack2 = [], []
    
    # Push all values from l1 onto stack1
    while l1:
        stack1.append(l1.val)
        l1 = l1.next
    
    # Push all values from l2 onto stack2
    while l2:
        stack2.append(l2.val)
        l2 = l2.next
    
    carry = 0
    result = None
    
    # While there are still digits in either stack
    while stack1 or stack2 or carry:
        sum = carry
        
        if stack1:  # If there's still a digit in stack1
            sum += stack1.pop()
        
        if stack2:  # If there's still a digit in stack2
            sum += stack2.pop()
        
        carry = sum // 10  # Calculate the new carry
        new_node = ListNode(sum % 10)  # Create a new node with the digit
        new_node.next = result  # Link the new node to the front of the result list
        result = new_node  # Update the result to the new node
    
    return result
← Back to All Questions