-
Notifications
You must be signed in to change notification settings - Fork 892
/
problem_127.py
72 lines (57 loc) · 1.78 KB
/
problem_127.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
FACTOR = 10
class Node:
def __init__(self, val):
self.val = val
self.next = None
def __repr__(self):
return "{} -> {}".format(self.val, self.next)
@staticmethod
def convert_num_to_list(num):
numstr = str(num)
dummy_head = Node(0)
prev = dummy_head
for num in numstr[::-1]:
curr = Node(int(num))
prev.next = curr
prev = curr
return dummy_head.next
@staticmethod
def convert_list_to_num(head):
curr = head
num = 0
factor = 1
while curr:
num += factor * curr.val
curr = curr.next
factor *= FACTOR
return num
@staticmethod
def add_nums(list_a, list_b):
new_dummy_head = Node(0)
prev_res = new_dummy_head
curr_a, curr_b = list_a, list_b
carry = 0
while carry or curr_a or curr_b:
res_digit = 0
if carry:
res_digit += carry
if curr_a:
res_digit += curr_a.val
curr_a = curr_a.next
if curr_b:
res_digit += curr_b.val
curr_b = curr_b.next
carry = res_digit // FACTOR
curr_res = Node(res_digit % FACTOR)
prev_res.next = curr_res
prev_res = curr_res
return new_dummy_head.next
assert Node.convert_list_to_num(
Node.add_nums(Node.convert_num_to_list(0),
Node.convert_num_to_list(1))) == 1
assert Node.convert_list_to_num(
Node.add_nums(Node.convert_num_to_list(1000),
Node.convert_num_to_list(1))) == 1001
assert Node.convert_list_to_num(
Node.add_nums(Node.convert_num_to_list(99),
Node.convert_num_to_list(25))) == 124