PadhaikoAll subjects

Past exam question: 2078 Chaitra (Regular), Q4

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

Topic: Linked List

Question

Consider two linked lists that represent two polynomials. Subtract them and return the difference as a linked list. Write an algorithm and program to implement above scenario.

Solution

Polynomial Representation Using Singly Linked List: Each term is stored in a node containing (coeff, exp, next), kept sorted in descending order of exponent exp. Computing walks both lists with pointers p1 and p2:

Algorithm SUBTRACT_POLY(p1, p2):

Algorithm SUBTRACT_POLY(p1, p2):
1. Initialize result = NULL, tail = NULL
2. While p1 != NULL and p2 != NULL:
       If p1->exp > p2->exp:
           APPEND(result, tail, p1->coeff, p1->exp)
           p1 = p1->next
       Else if p1->exp < p2->exp:
           APPEND(result, tail, -(p2->coeff), p2->exp)
           p2 = p2->next
       Else:
           diff = p1->coeff - p2->coeff
           If diff != 0:
               APPEND(result, tail, diff, p1->exp)
           p1 = p1->next
           p2 = p2->next
3. While p1 != NULL:
       APPEND(result, tail, p1->coeff, p1->exp)
       p1 = p1->next
4. While p2 != NULL:
       APPEND(result, tail, -(p2->coeff), p2->exp)
       p2 = p2->next
5. Return result

Complete C Program:

#include <stdio.h>
#include <stdlib.h>

typedef struct Term {
    int coeff;
    int exp;
    struct Term *next;
} Term;

Term *createNode(int c, int e) {
    Term *n = (Term *)malloc(sizeof(Term));
    n->coeff = c;
    n->exp = e;
    n->next = NULL;
    return n;
}

void appendTerm(Term **head, Term **tail, int c, int e) {
    if (c == 0) return;
    Term *n = createNode(c, e);
    if (*head == NULL) {
        *head = *tail = n;
    } else {
        (*tail)->next = n;
        *tail = n;
    }
}

Term *subtractPoly(Term *p1, Term *p2) {
    Term *res = NULL, *tail = NULL;
    while (p1 != NULL && p2 != NULL) {
        if (p1->exp > p2->exp) {
            appendTerm(&res, &tail, p1->coeff, p1->exp);
            p1 = p1->next;
        } else if (p1->exp < p2->exp) {
            appendTerm(&res, &tail, -p2->coeff, p2->exp);
            p2 = p2->next;
        } else {
            appendTerm(&res, &tail, p1->coeff - p2->coeff, p1->exp);
            p1 = p1->next;
            p2 = p2->next;
        }
    }
    while (p1 != NULL) {
        appendTerm(&res, &tail, p1->coeff, p1->exp);
        p1 = p1->next;
    }
    while (p2 != NULL) {
        appendTerm(&res, &tail, -p2->coeff, p2->exp);
        p2 = p2->next;
    }
    return res;
}

void displayPoly(Term *p) {
    if (!p) { printf("0\n"); return; }
    while (p) {
        printf("%+dx^%d ", p->coeff, p->exp);
        p = p->next;
    }
    printf("\n");
}

int main(void) {
    Term *p1 = NULL, *t1 = NULL, *p2 = NULL, *t2 = NULL;
    // P1(x) = 5x^3 + 4x^2 + 2
    appendTerm(&p1, &t1, 5, 3);
    appendTerm(&p1, &t1, 4, 2);
    appendTerm(&p1, &t1, 2, 0);
    // P2(x) = 3x^3 + 4x^2 - 6x + 1
    appendTerm(&p2, &t2, 3, 3);
    appendTerm(&p2, &t2, 4, 2);
    appendTerm(&p2, &t2, -6, 1);
    appendTerm(&p2, &t2, 1, 0);

    Term *diff = subtractPoly(p1, p2); // 2x^3 + 6x + 1
    displayPoly(diff);
    return 0;
}
Answer:

Both polynomials are stored as linked lists in descending exponent order. Merging them in a single pass copies unmatched P1 terms, negates unmatched P2 terms, subtracts coefficients on matching exponents (omitting zero terms), and returns the resulting difference linked list.

All past exam questions for Data Structure and Algorithms