Hi,
This is a problem from "Algorithms and data structures in C" book by Mark Allen Weiss.
A polynomial can be represented as a linked list . For eg.
2x^5 + 3x^3 + 2x + 1 can be represented as
2,5---3,3---2,1---1,0 (1st number in the node represents the coefficient and the 2nd number of the node represents the powerr to which the variable is raised )
Also the nodes are arranged in order of the powers as shown in the example.
The question is to multiply two polynomials represented as above in
O(MN*(log MN)) time complexity . (M and N are the number of terms in the lists each)
Also the order has to be maintained and there has to be only one term for each value of power.
Please provide hints for these above problem...
Thanks,
Vineet