Past exam question: 2078 Chaitra (Regular), Q4
Open in the Padhaiko appQuestion
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:
- If
p1->exp > p2->exp: append(p1->coeff, p1->exp)to result and advancep1. - If
p1->exp < p2->exp: append(-p2->coeff, p2->exp)to result and advancep2. - If
p1->exp == p2->exp: computediff = p1->coeff - p2->coeff; ifdiff != 0, append(diff, p1->exp); advance bothp1andp2. - Append remaining terms of
p1(with same sign) or remaining terms ofp2(with negated coefficient).
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 resultComplete 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.