Perform arithmetic on a singly linked list which represent a large number

Question

I have a linked list which represents the large number 2253239487.

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
        
def __repr__(self):
    return '{0}'.format(self.val)

The ListNode instance is populated as below:

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

Now, I want to divide the number by 3 and return the answer as a whole number.

I have written below code but it is giving wrong result:

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

There is an assumption that the "sum" integer is too big for the integer object. What is the best way to directly calculate avg without storing sum in memory?

Answer 1

If you can't represent the linked list as an integer, then you need to do long division on the values in the list. You can do this by iterating divide by 3 over the nodes to generate new nodes, and then joining the nodes before finally outputting the result:

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()

Output:

751079829

Note that if the divisor could be larger than the input number (for testing purposes) then this would give a string of 0s as the result. You can work around this by changing the if test to only add a leading 0 if we are at the last node in the list:

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()

Note also that if you generate your list in reverse order you can save all the assignments to .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)