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

Difficulty: Medium

Problem Description

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.

Key Insights

  • Each linked list represents a number in reverse order, meaning the head of the list contains the least significant digit.
  • We need to traverse both linked lists simultaneously and perform digit-wise addition, taking care of the carry from previous additions.
  • The resulting linked list will also be built in reverse order, which aligns with how we add digits.

Space and Time Complexity

Time Complexity: O(max(m, n)), where m and n are the lengths of the two linked lists. We may need to traverse both lists entirely.

Space Complexity: O(max(m, n)), for the resulting linked list that stores the sum.

Solution

The solution involves using a while loop to traverse both linked lists. We maintain a carry to account for sums that exceed 9. We create a new linked list for the result as we calculate the sum of corresponding digits from both input lists.

  1. Initialize a dummy node to simplify the result list construction.
  2. Use a pointer to track the current position in the result list.
  3. Initialize a carry variable to handle sums greater than 9.
  4. Traverse both linked lists until both are exhausted and there is no carry left:
    • Add corresponding digits and the carry.
    • Create a new node for the current sum modulo 10.
    • Update the carry for the next iteration.
  5. If there is any carry left after the loop, create a new node for it.
  6. Return the next node of the dummy node as the head of the result list.

Code Solutions

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

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)  # Create a dummy node
    current = dummy  # Pointer to build the new list
    carry = 0  # Initialize carry to 0
    
    while l1 or l2 or carry:
        val1 = (l1.val if l1 else 0)  # Get value from l1
        val2 = (l2.val if l2 else 0)  # Get value from l2
        total = val1 + val2 + carry  # Calculate sum
        
        carry = total // 10  # Update carry
        current.next = ListNode(total % 10)  # Create new node with the last digit
        current = current.next  # Move to the next node
        
        if l1: l1 = l1.next  # Move to the next node in l1
        if l2: l2 = l2.next  # Move to the next node in l2
    
    return dummy.next  # Return the next of dummy node
← Back to All Questions