Leetcode 2: Add Two Numbers

Problem description

Summary of Key Tricks

1. Simplify with a dummy head node:

• With dummy head: No special handling of the head node

dummy_head = ListNode(0)
current = dummy_head
list = head

while list:
    current.next = ListNode(some_value)
    current = current.next
    ...

# NOTE: It does not matter what value we initialize dummy_head with,
#   since we return its `next` in the end to get the result
return dummy_head.next

• Without a dummy head: Initializing, checking, and special handling of the head node becomes necessary

# Initialize result head with None
result_head = None
list = head

while list:
    # At beginning of building result list, we'd need to check
    #   and give head node special handlings
    if result_head is None:
        result_head = ListNode(some_value)
        current = result_head
    # Then handle non-head node with typical singly linked list traversal
    else:
        current.next = ListNode(some_value)   
        current = current.next
    ...

return result_head

2. Simulating the Full Adder: Although we can easily do additions by hand, quickly thinking of its implementation details in this context may not be as easy as we wish. A handy mnemonic to help us recall is “mod for the moment, divide for the drive”:

• mod for the moment (the current digit): total_sum % 10
• divide for the drive (the carry): total_sum // 10

3. Iterate through two linked lists simultaneously despite possible length differences: The length difference could be implicitly handled with an or condition: while l1 is not None or l2 is not None and if condition to control operations required for each list (i.e., if l1 is not None… and if l2 is not None )

4. Handling of the extra carry after completing two-list iteration: This could happen to additions such as adding 9 -> 9 with 1, where we get one extra carry of 1 to form a length-3 list

Python Implementation

Putting these together, we get the following implementation:

from typing import Optional


class ListNode:
    """Singly-linked list definition"""

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


class Solution:
    def addTwoNumbers(
        self, l1: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        # Create a dummy head
        dummy_head = ListNode(0)
        # Start traversal from dummy head
        current = dummy_head

        # Initialize carry
        carry = 0

        # Traverse two list simultaneously
        while l1 is not None or l2 is not None:
            # At each traversal advancement,
            #   initialize total_sum at this step
            #   with `carry`` from previous addition
            total_sum = carry

            if l1 is not None:
                total_sum += l1.val
                # good old list traversal: advance to next node
                l1 = l1.next

            if l2 is not None:
                total_sum += l2.val
                # good old list traversal: advance to next node
                l2 = l2.next

            # Process the sum: "mod for the moment; divide for the drive"
            current.next = ListNode(total_sum % 10)
            carry = total_sum // 10

            # Advance to next node
            current = current.next

        
        # Take care of the extra carry after completing traversal 
        if carry > 0:
            current.next = ListNode(carry)

        # When extracting result,
        #   we skip dummy head itself and return its next
        return dummy_head.next

Space and Time Complexity

Given m and n denote the length of the two lists l1 and l2, respectively:

• Space complexity: The result list itself has a size of max(m, n) + 1, where the +1 comes from the dummy_head itself. Translate to big O, we have a space complexity of O(max(m, n))
• Time complexity: We traverse two list in one go, which gives us a time complexity of O(max(m, n))

Unit Test Examples (With pytest)

# Set up helper functions
def list_to_linkedlist(nums):
    dummy_head = ListNode(0)
    current = dummy_head

    for num in nums:
        current.next = ListNode(num)
        current = current.next

    return dummy_head.next


def linkedlist_to_list(head):
    nums = []
    current = head

    while current:
        nums.append(current.val)
        current = current.next

    return nums


def test_addTwoNumbers():
    # Case 1: Simple, equal lengths case
    l1 = list_to_linkedlist([1, 2, 3])
    l2 = list_to_linkedlist([1, 1, 1])
    result = Solution().addTwoNumbers(l1, l2)
    assert linkedlist_to_list(result) == [2, 3, 4]

    # Case 2: Extra carry
    l1 = list_to_linkedlist([9, 9, 9])
    l2 = list_to_linkedlist([1])
    result = Solution().addTwoNumbers(l1, l2)
    assert linkedlist_to_list(result) == [0, 0, 0, 1]