Interview challenge · medium · linked-list, math
Add Two Numbers
El reto
El enunciado va en inglés, igual que en el vídeo.
Two non-negative numbers are stored as linked lists, one digit per node, with the ones digit first (reverse order). Add them and return the sum as a linked list in the same format. The lists can have different lengths.
Example
2 -> 4 -> 3 + 5 -> 6 -> 4 -> 7 -> 0 -> 8 (342 + 465 = 807)
9 -> 9 -> 9 + 1 -> 0 -> 0 -> 0 -> 1 (999 + 1 = 1000)Idea: add like on paper. Because the lists start with the ones digit, you can walk both from the head: at each step add the two digits (or 0 when a list has ended) plus the carry, write the last digit of that sum in a new node and carry the rest to the next step. Keep going while either list has nodes or the carry is not zero: that last carry is the extra digit in 999 + 1. A dummy head node saves the special case for the first digit. Time O(n + m).
La solución
# Add Two Numbers - ayotl.dev
class Node:
def __init__(self, val, next=None):
self.val, self.next = val, next
def add(a, b):
head = tail = Node(0) # dummy head
carry = 0
# like on paper: digit + digit + carry
while a or b or carry:
s = carry
if a:
s, a = s + a.val, a.next
if b:
s, b = s + b.val, b.next
# keep one digit, carry the rest
carry, d = divmod(s, 10)
tail.next = Node(d)
tail = tail.next
return head.next
def show(n):
while n:
end = " -> " if n.next else "\n"
print(n.val, end=end)
n = n.next
a = Node(2, Node(4, Node(3))) # 342
b = Node(5, Node(6, Node(4))) # 465
show(add(a, b))
c = Node(9, Node(9, Node(9))) # 999
show(add(c, Node(1)))
$ python3 add_two_numbers.py
7 -> 0 -> 8
0 -> 0 -> 0 -> 1