Вопрос (из: «взлом собеседования по кодированию»):
У вас есть два числа, представленные в виде связанного списка, где каждый узел содержит одну цифру.Цифры хранятся в обратном порядке, так что цифра 1 находится в начале списка.Напишите функцию, которая добавляет два числа и возвращает сумму в виде связанного списка.
ПРИМЕР
Ввод: (3 -> 1 -> 5) + (5 -> 9 -> 2)
Выход:8 -> 0 -> 8
Мой код:
#Define node and convenience methods
class Node(object):
def __init__(self,data = None, next_node = None):
self.data = data
self.next_node = next_node
def get_data(self):
return self.data
def get_next(self):
return self.next_node
def set_next(self, new_next):
self.next_node = new_next
#Make first linked list
class LinkedList1(object):
def __init__(self, head = None):
self.head = head
def insert(self, data):
new_node = Node(data)
new_node.set_next(self.head)
self.head = new_node
#iterate through the list and save a list of the numbers
def iterate(self):
current = self.head
list1 = []
while current:
list1.append(current.get_data())
current = current.get_next()
return list1
#Define second linked list
class LinkedList2(object):
def __init__(self, head = None):
self.head = head
def insert(self, data):
new_node = Node(data)
new_node.set_next(self.head)
self.head = new_node
#iterate through the list and save a list of the numbers
def iterate(self):
current = self.head
list2 = []
while current:
list2.append(current.get_data())
current = current.get_next()
return list2
object1 = LinkedList1()
object2 = LinkedList2()
#Define resulting linked list and print it
class New(object):
def __init__(self,head = None):
self.head = head
def linked_list(self, new_list1):
for i in new_list1:
new_node = Node(i)
new_node.set_next(self.head)
self.head = new_node
def printing(self):
current = self.head
while current:
print(current.get_data(), end = " ")
current = current.get_next()
return
no1 = object1.iterate()
no2 = object2.iterate()
new_list = []
#Calculate sum recursively
def sum_calc(carry):
sum1 = 0
while no1 and no2:
sum1 = no1.pop(0) + no2.pop(0) + carry
if sum1 > 10:
new_list.append(sum1 % 10)
sum_calc(1)
else:
new_list.append(sum1)
sum_calc(0)
#If any elements left in no1
if no1:
new_list.extend(no1)
#If any elements left in no2
elif no2:
new_list.extend(no2)
else:
return new_list
object3 = New()
passing = []
while True:
print("1.Insert in list 1")
print("2.Insert in list 2")
print("3.Sum")
print("4.New List of sum")
print("5.Exit")
option = (int)(input("option: "))
if option == 1:
data = (int)(input("Data: "))
object1.insert(data)
elif option == 2:
data = (int)(input("Data: "))
object2.insert(data)
elif option == 3:
#Initial carry = 0 when adding unit's digits
passing = sum_calc(0)
elif option == 4:
object3.linked_list(passing)
object3.printing()
print()
else:
break
Но всякий раз, когда option ==4
, он ничего не печатает и переходит к следующей итерации цикла while.
Я знаю, что это не лучшее решение, но может ли кто-нибудь помочь указать на ошибку или ошибку в алгоритмическом мышлении?Спасибо!