对表示大量数字的单向链表执行算术

Question

我有一个链表，它表示大量的2253239487.

class ListNode:
def __init__(self, val, next=None):
self.val = val
self.next = next

def __repr__(self):
return '{0}'.format(self.val)

ListNode实例填充如下：

h1 = ListNode(2)
n2 = ListNode(2)
n3 = ListNode(5)
n4 = ListNode(3)
n5 = ListNode(2)
n6 = ListNode(3)
n7 = ListNode(9)
n8 = ListNode(4)
n9 = ListNode(8)
n10 = ListNode(7)
h1.next = n2
n2.next = n3
n3.next = n4
n4.next = n5
n5.next = n6
n6.next = n7
n7.next = n8
n8.next = n9
n9.next = n10

现在，我想divide the number by 3并return答案作为whole number.

我在下面写了代码，但它给出了错误的结果：

sum = 0
head = h1
while head.next:
sum += head.val
head = head.next
return sum // 3

有一个假设，即"sum"整数对于整数对象来说太大了。直接计算平均值而不将总和存储在内存中的最佳方法是什么？

Answer 1

如果不能将链表表示为整数，则需要对列表中的值进行长除法。为此，您可以在节点上迭代除以 3 以生成新节点，然后在最终输出结果之前加入节点：

divisor = 3
nodes = []
head = h1
r = 0
while head:
v = r * 10 + head.val
q = v // divisor
r = v % divisor
if q != 0 or head != h1:
nodes.append(ListNode(q))
head = head.next
for i, n in enumerate(nodes[:-1]):
n.next = nodes[i+1]
head = nodes[0]
while head:
print(head.val, end='')
head = head.next
print()

输出：

751079829

请注意，如果除数可能大于输入数字(用于测试目的)，那么这将给出一个0s 的字符串作为结果。您可以通过将if测试更改为仅在列表中最后一个节点添加前导0来解决此问题：

divisor = 3
nodes = []
head = h1
r = 0
while head:
v = r * 10 + head.val
q = v // divisor
r = v % divisor
if q != 0 or len(nodes) > 0 or head.next is None:
nodes.append(ListNode(q))
head = head.next
for i, n in enumerate(nodes[:-1]):
n.next = nodes[i+1]
head = nodes[0]
while head:
print(head.val, end='')
head = head.next
print()

另请注意，如果以相反的顺序生成列表，则可以将所有作业保存到.next：

n10 = ListNode(7)
n9 = ListNode(8, n10)
n8 = ListNode(4, n9)
n7 = ListNode(9, n8)
n6 = ListNode(3, n7)
n5 = ListNode(2, n6)
n4 = ListNode(3, n5)
n3 = ListNode(5, n4)
n2 = ListNode(2, n3)
h1 = ListNode(2, n2)