Add Two Numbers medium

Problem Statement

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.

Example 1:

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]

Steps

  1. Initialization: Create a dummy node to simplify the handling of the head of the result list. Initialize a carry variable to 0.
  2. Iteration: Iterate through the linked lists l1 and l2 simultaneously. If either list is shorter than the other, treat the missing nodes as having a value of 0.
  3. Summation: For each pair of nodes, calculate the sum of their values plus the carry from the previous iteration.
  4. Node Creation: Create a new node with the value of the sum modulo 10 (the units digit).
  5. Carry Update: Update the carry variable to the sum divided by 10 (the tens digit).
  6. List Building: Append the newly created node to the result list.
  7. Remaining Nodes: If one list is longer than the other, continue iterating through the remaining nodes of the longer list, adding them to the result list along with the carry.
  8. Final Carry: If a carry remains after iterating through all nodes, create a new node with the carry value and append it to the result list.
  9. Return Value: Return the head of the result list (excluding the dummy node).

Explanation

The algorithm efficiently handles addition of arbitrarily long numbers represented as linked lists. The use of a dummy node simplifies the process of creating and linking new nodes, especially when handling the initial node of the result list. The carry variable ensures that the algorithm correctly propagates the carry-over from one digit to the next, accurately simulating addition. The modulo and division operations extract the units and tens digits, respectively, of the sum.

Code

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

def addTwoNumbers(l1, l2):
    dummy = ListNode(0)  # Dummy node to simplify head handling
    current = dummy
    carry = 0

    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0

        sum_val = val1 + val2 + carry
        carry = sum_val // 10  # Integer division for carry
        digit = sum_val % 10   # Modulo for the digit

        current.next = ListNode(digit)
        current = current.next

        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None

    return dummy.next  # Exclude the dummy node


# Example Usage
l1 = ListNode(2, ListNode(4, ListNode(3)))
l2 = ListNode(5, ListNode(6, ListNode(4)))

result = addTwoNumbers(l1, l2)

while result:
    print(result.val, end=" ") # Output: 7 0 8
    result = result.next
print() #Add a newline for clean output

l1 = ListNode(0)
l2 = ListNode(0)
result = addTwoNumbers(l1,l2)
while result:
    print(result.val, end=" ") #Output: 0
    result = result.next
print()


l1 = ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))))
l2 = ListNode(9, ListNode(9, ListNode(9, ListNode(9))))
result = addTwoNumbers(l1,l2)
while result:
    print(result.val, end=" ") #Output: 8 9 9 9 0 0 0 1
    result = result.next
print()

Complexity

  • Time Complexity: O(max(m, n)), where 'm' and 'n' are the lengths of the input linked lists. We iterate through the lists at most once.
  • Space Complexity: O(max(m, n)) in the worst case, as the length of the resulting linked list can be at most one element longer than the longer of the two input lists (to accommodate a final carry). The space used by the algorithm itself is constant beyond the output linked list.