Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Imperative programming (resit) / 4 / b / Solution

Remove zero nodes while retaining every nonzero node and its order:

PROCEDURE normalise(VAR r: poly);
VAR p,prev: poly;
BEGIN
  p := r; prev := NIL;
  WHILE p # NIL DO
    IF p.coeff = 0 THEN
      IF prev = NIL THEN r := p.next
      ELSE prev.next := p.next END
    ELSE
      prev := p
    END;
    p := p.next
  END
END normalise;

At each step, the processed prefix contains precisely the nonzero nodes already examined, and prev is its final node or NIL. Thus removal at the head, consecutive removals and removal of every node are handled. This linked-list deletion pass takes linear time in the original node count. It does not by itself combine duplicate powers.