Past exam question: 2078 Poush (Back), Q2(b)
Open in the Padhaiko appQuestion
How do you represent polynomial equation using linked list? Write an algorithm to add two polynomial equations using linked list.
Solution
Polynomial Representation Using a Linked List: A single-variable polynomial is represented as a singly linked list in descending order of exponents, where each node has three fields:
coeff: numeric coefficient of the term.exp: non-negative integer exponent of .next: pointer to the next lower-degree term (orNULL).
Only non-zero terms are stored, making sparse polynomials space-efficient.
Algorithm ADD_POLY(p1, p2):
Algorithm ADD_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:
sum = p1->coeff + p2->coeff
If sum != 0:
APPEND(result, tail, sum, 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 resultAnswer:
Each non-zero term is stored as a node (coeff, exp, next) ordered by decreasing exp. ADD_POLY merges two sorted polynomial lists in time by copying larger-exponent terms directly and summing coefficients when exponents match.