Question 5 of 9: Linked Lists — Building and Adding Polynomials

Question 5: Linked Lists — Building and Adding Polynomials (20 marks: (a) 5, (b) 15)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. A node type holding an integer coefficient, an integer exponent and a link; a list invariant of strictly decreasing exponents with positive coefficients; input pairs already sorted by exponent and terminated by the pair (0,0).

Find. Two functions: one that reads the terminated stream of pairs and returns the head of a newly built list; one that returns a newly built list representing the sum of two such polynomials.

Approach. Build by tail-appending so the input order is preserved in one pass; add by merging the two ordered lists in a single sweep, exactly as in the merge step of merge sort, emitting the higher exponent at each comparison and summing on a tie.

/* As printed in the question -- this does NOT compile: the tag
   polynomial_node is not yet in scope inside the struct, and the struct
   itself is anonymous, so the "next" pointer has no type to point at. */
typedef struct {
    int coefficient;
    int exponent;
    polynomial_node *next;
} polynomial_node;

/* The correct self-referential form: give the struct a TAG and refer to
   "struct polynomial_node" inside its own definition. */
typedef struct polynomial_node {
    int coefficient;
    int exponent;
    struct polynomial_node *next;
} polynomial_node;

(a) get_polynomial (5 marks)

1. Append at the tail, do not prepend at the head. The input pairs already arrive in decreasing exponent order, which is exactly the order the list must hold, so the list is built by adding each new node behind the previous one. Keeping a tail pointer makes each append $O(1)$ and the whole build $O(n)$; prepending would be equally cheap but would reverse the polynomial, breaking the invariant.
2. Stop on the sentinel, not on end of file alone. The pair (0,0) terminates the data. Testing scanf(...) == 2 as well means a truncated input stream cannot spin the loop forever.

   #include <stdio.h>
   #include <stdlib.h>
   
   /* Allocate one node, or fail loudly. */
   static polynomial_node *new_node(int c, int e)
   {
       polynomial_node *n = malloc(sizeof *n);
       if (n == NULL) {
           fprintf(stderr, "out of memory\n");
           exit(EXIT_FAILURE);
       }
       n->coefficient = c;
       n->exponent    = e;
       n->next        = NULL;
       return n;
   }
   
   polynomial_node *get_polynomial(void)
   {
       polynomial_node *head = NULL, *tail = NULL, *node;
       int c, e;
   
       while (scanf("%d %d", &c, &e) == 2) {
           if (c == 0 && e == 0)          /* the (0,0) sentinel ends the input */
               break;
   
           node = new_node(c, e);
   
           if (head == NULL)              /* first node: it becomes the head */
               head = node;
           else                           /* otherwise append behind the tail */
               tail->next = node;
   
           tail = node;                   /* O(1) append keeps the input order */
       }
       return head;
   }

(b) add_polynomials (15 marks)

1. Recognise the operation as a merge. Both operands are sorted by decreasing exponent, and the sum must be too. Repeatedly taking the larger of the two leading exponents — and summing when they are equal — emits terms in exactly the required order: $$\boxed{\text{compare leading exponents} \Rightarrow \begin{cases} e_{1} > e_{2} & \text{copy the term from } p_1\\ e_{1} < e_{2} & \text{copy the term from } p_2\\ e_{1} = e_{2} & \text{emit } (c_{1}+c_{2}) \text{ if non-zero} \end{cases}}$$ Each comparison consumes at least one input node, so the merge is $O(m+n)$ in time and allocates exactly as many nodes as the answer has terms.
2. Drop cancelling terms rather than storing a zero. When two equal exponents carry coefficients that sum to zero, emitting a node would violate the representation, which stores only non-zero terms — and would leave a term that later operations must keep special-casing. The continue in the equal-exponent branch is therefore load-bearing. (The question states coefficients are positive, so cancellation cannot arise from its own data; guarding for it costs one line and makes the function safe for the subtraction that any real polynomial package would add next.)
3. Use a dummy head node to remove the special case. Without it, every append needs a test for “is this the first node?”. With a local dummy whose next field accumulates the answer, the loop body is uniform, and only head.next — a pointer to heap memory, not to the local — escapes the function.
4. Drain whichever list is left over. When one operand runs out, every remaining term of the other has a lower exponent than anything already emitted, so the remainder appends unchanged. Copying rather than splicing keeps the promise in the question that the result is a newly created list: neither operand is modified or aliased, so the caller may still use or free both.

   polynomial_node *add_polynomials(polynomial_node *p1, polynomial_node *p2)
   {
       polynomial_node head;              /* dummy: removes the "is it first?" test */
       polynomial_node *tail = &head;
       int c, e;
   
       head.next = NULL;
   
       while (p1 != NULL && p2 != NULL) {
   
           if (p1->exponent == p2->exponent) {
               c = p1->coefficient + p2->coefficient;
               e = p1->exponent;
               p1 = p1->next;
               p2 = p2->next;
               if (c == 0)
                   continue;              /* the terms cancelled: emit nothing */
   
           } else if (p1->exponent > p2->exponent) {
               c = p1->coefficient;  e = p1->exponent;  p1 = p1->next;
   
           } else {
               c = p2->coefficient;  e = p2->exponent;  p2 = p2->next;
           }
   
           tail->next = new_node(c, e);
           tail = tail->next;
       }
   
       /* At most one list still has terms; they are all of lower degree than
          anything already emitted, so they append unchanged. */
       for (; p1 != NULL; p1 = p1->next) {
           tail->next = new_node(p1->coefficient, p1->exponent);
           tail = tail->next;
       }
       for (; p2 != NULL; p2 = p2->next) {
           tail->next = new_node(p2->coefficient, p2->exponent);
           tail = tail->next;
       }
   
       return head.next;                  /* the dummy is a local; only its link escapes */
   }

5. Verify on a worked example. With $p_{1}(x) = 5x^{4} + 3x^{2} + 7$ and $p_{2}(x) = 2x^{4} + 4x^{3} + 6x^{2}$, the merge emits $(5+2)x^{4}$, then $4x^{3}$ from $p_2$ alone, then $(3+6)x^{2}$, then $7$ from $p_1$ alone: $$\boxed{p_{1}(x)+p_{2}(x) = 7x^{4} + 4x^{3} + 9x^{2} + 7}$$ Evaluating both sides at $x = 2$ gives $80+12+7 = 99$ for $p_1$ and $32+32+24 = 88$ for $p_2$ (which has no constant term), and $99 + 88 = 187 = 112+32+36+7$ — the sum list evaluates to 187 at $x = 2$, as it must.