Use a helper whose first argument is a private result list. It adds a coefficient to an existing power, deleting a cancellation, or allocates a new node:
accumulate(VAR r: poly; c: T; e: INTEGER):
if c == 0: return
p = r; prev = NIL
while p != NIL and p.power != e:
prev = p; p = p.next
if p == NIL:
q = new term(c,e,r)
r = q
else:
p.coeff = p.coeff+c
if p.coeff == 0:
if prev == NIL: r = p.next
else: prev.next = p.next
addPoly(x,y):
r = NIL
p = x
while p != NIL:
accumulate(r,p.coeff,p.power)
p = p.next
p = y
while p != NIL:
accumulate(r,p.coeff,p.power)
p = p.next
return rHere
VAR applies to the list variable r; coefficients and powers are value arguments. The helper preserves one node per power and excludes zero coefficients. After each loop iteration, the result represents exactly the processed input terms. Every result node is fresh, so neither input's nodes or links are changed, even if the two inputs alias or share tails. For unsorted inputs of lengths , a simple worst-case bound is for these repeated scans. Articles by others on the same topic
There are currently no matching articles.