c - How to use linked list to implement the multiplication of two polynomial in O(M^2N)? -

this exercise "data structure , algorithm analysis in c", exercise 3.7. assume there 2 polynomials implemented in linked list. 1 has m terms. has n terms. exercise ask me implement multiplication of 2 polynomial in o(m^2n)(assume m smaller one). how solve this?

i can give idea.

suppose polynomials 1+x+x^3 , 1+x^2.

create linked list p using (1,1)--->(1,1)--->(1,3)

create linked list q (1,1)--->(1,2) (a,b) denotes coefficient of x^b.

now each node in p, multiply each node of q.

how? create node res (x,y)

x= p->coeff * q->coeff.

and y=p->exp+q->exp.

add new node polynomial contain answer.

---

during insertion in answer polynomial have keep in mind 2 things-

i) keep sorted list (sorted against exp)(increasing maybe have takem increasing here--you can take decreasing also).

ii) correct position in case add new node , if node same exp value exists add coeff , delete node insert.

ok! print polynomial.

the complexity analysis.