algoadvance

Problem Statement

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.

Example:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7, 8, 0, 7]

Constraints:

Clarifying Questions

  1. Can the lists have different lengths?
    • Yes, the lists can have different lengths.
  2. Do we need to handle very large numbers?
    • Since the input size is limited to 100 nodes, Python’s integer handling can manage this without issue.
  3. Do we have any leading zeros in the input lists?
    • No, the input lists do not have leading zeros except for the number 0 itself.

Strategy

  1. Convert the linked lists to numbers: We will traverse each linked list and convert it to the corresponding integer value.
  2. Add the numbers: Use basic integer addition to sum the converted values.
  3. Convert the result back to a linked list: Create a new linked list from the sum of the numbers.

Our goal is to handle the most significant digit being first (as opposed to the usual problem where the least significant digit comes first), so we need to manage the numbers carefully.

Code

Below is the Python code to solve the problem:

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

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    # Function to convert linked list to stack
    def to_stack(l: ListNode) -> [int]:
        stack = []
        while l:
            stack.append(l.val)
            l = l.next
        return stack
    
    # Convert both numbers to stacks
    s1, s2 = to_stack(l1), to_stack(l2)
    
    carry = 0
    head = None
    
    # While there is something to add
    while s1 or s2 or carry:
        sum_value = carry
        if s1:
            sum_value += s1.pop()
        if s2:
            sum_value += s2.pop()
        
        # Calculate new carry and digit
        carry, val = divmod(sum_value, 10)
        
        # Create new node and put it at the front
        new_node = ListNode(val)
        new_node.next = head
        head = new_node
        
    return head

Time Complexity

Breaking down the complexity:

Since these operations are sequential and not nested, the overall time complexity is O(n), where n is the length of the longer list. This accounts for traversing and processing each node a single time.

The space complexity is also O(n) due to using stacks to store the list values before producing the result.

Try our interview co-pilot at AlgoAdvance.com