Walking two lists at once with a carry

Arithmetic on lists, and the loop condition that handles both lists ending at different times.

Key idea

The shape

Walking two lists in parallel and combining them position by position is a common shape, and the interesting part is when to stop. There are three reasons to keep looping: the first list has more, the second has more, or there is something left over from the previous step.

Writing the condition as all three joined by or handles unequal lengths and a trailing carry without any special cases after the loop.

1class Node:2    def __init__(self, val, next=None):3        self.val, self.next = val, next4 5def build(values):6    head = None7    for value in reversed(values):8        head = Node(value, head)9    return head10 11def to_list(node):12    out = []13    while node:14        out.append(node.val)15        node = node.next16    return out17 18def add_digit_lists(a, b):19    """Each list holds digits with the least significant first."""20    dummy = Node(0)21    tail = dummy22    carry = 023 24    while a or b or carry:25        total = carry26        if a:27            total += a.val28            a = a.next29        if b:30            total += b.val31            b = b.next32        carry, digit = divmod(total, 10)33        tail.next = Node(digit)34        tail = tail.next35 36    return dummy.next37 38print(to_list(add_digit_lists(build([2, 4, 3]), build([5, 6, 4]))))39print(to_list(add_digit_lists(build([9, 9]), build([1]))))

Predict the output· 5 min

Predict the output: dropping the carry from the condition

This version stops as soon as both lists are exhausted, ignoring a leftover carry. Type what it prints.

Python

1class Node:2    def __init__(self, val, next=None):3        self.val, self.next = val, next4 5def build(values):6    head = None7    for value in reversed(values):8        head = Node(value, head)9    return head10 11def to_list(node):12    out = []13    while node:14        out.append(node.val)15        node = node.next16    return out17 18def add_broken(a, b):19    dummy = Node(0)20    tail = dummy21    carry = 022    while a or b:23        total = carry24        if a:25            total += a.val26            a = a.next27        if b:28            total += b.val29            b = b.next30        carry, digit = divmod(total, 10)31        tail.next = Node(digit)32        tail = tail.next33    return dummy.next34 35print(to_list(add_broken(build([9, 9]), build([1]))))

Printed output

Problem· 22 min

Add Two Numbers

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1class Node:2 def __init__(self, val, next=None):3 self.val, self.next = val, next4 5def build(values):6 head = None7 for value in reversed(values):8 head = Node(value, head)9 return head10 11def to_list(node):12 out = []13 while node:14 out.append(node.val)15 node = node.next16 return out17 18def add_digit_lists(a, b):19 """Each list holds digits with the least significant first."""20 dummy = Node(0)21 tail = dummy22 carry = 023 24 while a or b or carry:25 total = carry26 if a:27 total += a.val28 a = a.next29 if b:30 total += b.val31 b = b.next32 carry, digit = divmod(total, 10)33 tail.next = Node(digit)34 tail = tail.next35 36 return dummy.next37 38print(to_list(add_digit_lists(build([2, 4, 3]), build([5, 6, 4]))))39print(to_list(add_digit_lists(build([9, 9]), build([1]))))

1class Node:2 def __init__(self, val, next=None):3 self.val, self.next = val, next4 5def build(values):6 head = None7 for value in reversed(values):8 head = Node(value, head)9 return head10 11def to_list(node):12 out = []13 while node:14 out.append(node.val)15 node = node.next16 return out17 18def add_broken(a, b):19 dummy = Node(0)20 tail = dummy21 carry = 022 while a or b:23 total = carry24 if a:25 total += a.val26 a = a.next27 if b:28 total += b.val29 b = b.next30 carry, digit = divmod(total, 10)31 tail.next = Node(digit)32 tail = tail.next33 return dummy.next34 35print(to_list(add_broken(build([9, 9]), build([1]))))