Polynomial addition using linked list

A polynomial is stored as a linked list where each node holds one non-zero term: its coefficient, its exponent and a link to the next term. Terms are kept in decreasing order of exponent, so two polynomials can be added by walking through both lists together (like merging).

struct term {
    int coef;           /* coefficient */
    int exp;            /* exponent    */
    struct term *next;
};

Example

P = 5x³ + 4x² + 2 and Q = 3x³ − 4x² + 7x + 1

P: [5|3]->[4|2]->[2|0]->NULL
Q: [3|3]->[-4|2]->[7|1]->[1|0]->NULL

Algorithm (p points to P, q to Q, R is the result list)

1. Set p and q to the first nodes; R is empty.
2. While p != NULL and q != NULL:
   • if p->exp > q->exp: append (p->coef, p->exp) to R; p = p->next.
   • else if p->exp < q->exp: append (q->coef, q->exp) to R; q = q->next.
   • else (equal exponents): sum = p->coef + q->coef; if sum ≠ 0 append (sum, p->exp) to R; move both p and q.
3. Copy the remaining nodes of whichever list is not finished to R.
4. Return R.

Trace

Result: R = 8x³ + 7x + 3 (checked by running the C code below).

struct term *add(struct term *p, struct term *q) {
    struct term head, *t = &head;     /* dummy head simplifies appending */
    head.next = NULL;
    while (p && q) {
        if (p->exp > q->exp)      { t->next = mk(p->coef, p->exp); p = p->next; t = t->next; }
        else if (p->exp < q->exp) { t->next = mk(q->coef, q->exp); q = q->next; t = t->next; }
        else {
            int s = p->coef + q->coef;
            if (s != 0) { t->next = mk(s, p->exp); t = t->next; }
            p = p->next; q = q->next;
        }
    }
    for (; p; p = p->next) { t->next = mk(p->coef, p->exp); t = t->next; }
    for (; q; q = q->next) { t->next = mk(q->coef, q->exp); t = t->next; }
    return head.next;
}

mk(c, e) allocates a node with coefficient c, exponent e and next = NULL. Time is O(m + n) for lists of m and n terms.