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

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?

CodePudding user response：

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:

nodes = []
head = h1
r = 0
while head:
    v = r * 10   head.val
    q = v // 3
    r = v % 3
    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 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)