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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Add Two Numbers II

Number: 445

Difficulty: Medium

Paid? No

Companies: Microsoft, Bloomberg, TikTok, Amazon, Apple

Problem Description

Given two non-empty linked lists representing two non-negative integers with their most significant digit coming first, compute their sum and return it as a linked list. Each node contains a single digit, and the numbers do not have any extra leading zeros. The challenge is to complete this task without reversing the input lists (i.e., by using an alternative approach).

Key Insights

  • Use stacks to simulate processing the digits from least significant (end of the list) to most significant (start of the list).
  • By pushing each list’s values onto a stack, you can pop them off in reverse order and perform addition with a carry.
  • Create new nodes for the resulting linked list as you compute the sum, linking them appropriately in reverse order.
  • Careful handling of the carry value is critical for correct summation.

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) due to the use of stacks to hold the nodes' values and the space needed for the result list.

Solution

We begin by pushing the values of each linked list onto two separate stacks, which allows us to retrieve the digits in reverse order for addition. Then we pop elements from both stacks, add them along with any carry from the previous addition, and create a new node for each digit of the resultant sum. Finally, the new nodes are prepended to the resultant list. This approach avoids modifying the input lists (i.e., no reversal is performed on the original linked lists) and handles different list lengths and carry propagation gracefully.

Code Solutions

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

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    # Initialize two stacks for the two numbers.
    stack1 = []
    stack2 = []
    
    # Push all nodes' values of l1 onto stack1.
    while l1:
        stack1.append(l1.val)
        l1 = l1.next

    # Push all nodes' values of l2 onto stack2.
    while l2:
        stack2.append(l2.val)
        l2 = l2.next

    carry = 0
    result = None  # This will be the head of the resulting linked list.

    # Process stacks until both are empty.
    while stack1 or stack2 or carry:
        # Get the top values from stacks if available.
        val1 = stack1.pop() if stack1 else 0
        val2 = stack2.pop() if stack2 else 0

        # Calculate the total sum of values and carry.
        total = val1 + val2 + carry
        carry = total // 10
        newNode = ListNode(total % 10)
        
        # Prepend the new node to the result list.
        newNode.next = result
        result = newNode

    return result

# Example usage:
# l1 = ListNode(7, ListNode(2, ListNode(4, ListNode(3))))
# l2 = ListNode(5, ListNode(6, ListNode(4)))
# head = addTwoNumbers(l1, l2)
← Back to All Questions