-
Notifications
You must be signed in to change notification settings - Fork 0
/
-2_add-two-numbers.py
160 lines (136 loc) · 5.27 KB
/
-2_add-two-numbers.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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
# Definition of a singly linked list
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
###############
# MY SOLUTION #
###############
def addTwoNumbers(l1, l2):
# the first number is l1
first_num = l1
# create an empty list to fill in with the first number
first_list = []
# the second number is l2
second_num = l2
# create an empty list to fill in with the second number
second_list = []
# create two variables that point to the same linked list
dummy = ListNode()
result = dummy
# deconstruct the first linked list into a list
# add the numbers in as a string to allow for the below manipulations
while first_num is not None:
first_list.append(str(first_num.val))
first_num = first_num.next
# deconstruct the second linked list into a list
# add the numbers in as a string to allow for the below manipulations
while second_num is not None:
second_list.append(str(second_num.val))
second_num = second_num.next
# the output of the above while loops returns a number that is reversed
# so the list needs to be reversed
first_list.reverse()
second_list.reverse()
# join list of separate numbers into a single string of the numbers to add
str_first_num = ''.join(first_list)
str_second_num = ''.join(second_list)
# add the two numbers together
num = int(str_first_num) + int(str_second_num)
# trun that back into a string
num = str(num)
# create a list from the string
ans_list = [letter for letter in num]
# reverse the list to enter it into the linked list
ans_list.reverse()
# this is the most challenging thing to understand for me
# two helpful Python linked list concepts:
# 1. when ListNode() is called a new "box" is made,
# 2. when a value is assigned to .next a new pointer is drawn (or moved)
# applying these concepts to the below for loop these images can be drawn:
# before iteration 1: result and dummy point to the same location
# in memory containing the same value of 0
#
# result dummy
# \ /
# \ /
# \ /
# ---------
# | 0 |
# ---------
#
# iteration 1:
# result.next() = ListNode(int(letter))
# draws a new pointer to a node that contains the first number
#
# result dummy
# \ /
# \ /
# ---------
# | x |
# ---------
# |
# ---------
# | y |
# ---------
#
# result = result.next
# assigns result to the value of result.next, which points to the
# second linked list value
#
# result dummy
# | /
# | /
# | ---------
# | | x |
# | ---------
# | |
# | ---------
# --->| y |
# ---------
#
# after iterating over the whole list, the linked list will be complete
# with result pointing to the last item in the list and dummy pointing to
# the entire linked list.
#
# Ideal naming would not be "result" and "dummy"
# Better would be "current_result" and "container"
for letter in ans_list:
result.next = ListNode(int(letter))
result = result.next
# dummy.next is returned because the first value in dummy is 0
# (see the linked list definition above)
return dummy.next
######################
# DIFFERENT SOLUTION #
######################
def addTwoNumbers(l1, l2):
# initialize the linked list
container = ListNode()
current_result = container
# remember the carry
carry = 0
while (l1 or l2 or carry):
# pull the first values from each input linked list
l1_value = l1.val if l1 is not None else 0
l2_value = l2.val if l2 is not None else 0
# new digit to insert into the final result
insert_value = l1_value + l2_value + carry
# get the carry
# floor division is used so that when the insert_value is >10,
# the carry is 1 and with the insert_value is <10, the carry is 0
# another way of saying this is:
# carry = 1 if carry > 10 else 0
carry = insert_value // 10
# then, keep only the ones place of the insert_value, since we removed
# the 1 in the tens place above
# if the insert value is >10, this operation gives the ones place
# if the insert value is <10, this operation keeps the insert_value the same
insert_value = insert_value % 10
# insert the value into the linked list
current_result.next = ListNode(insert_value)
# update pointers
current_result = current_result.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return container.next