Please try to use the exact input and output for testing. thanks.

1[25 Points] Sparse Polynomial Polynomial of degree N: CNXN + CN-1XN-1 + ... +cix + co (en # 0) A Sparse Polynomial (one with only a few of the coefficients being non-zeroes) can be represented using a linked list with the following node structure. power coeft first next For example, the linked list for the polynomial 9x? - 12x + 6x4 + 3x 2 is shown below. first 7 5 4 1 0 -12 6 3 -2 Write a program to add two sparse polynomial represented using linked list as shown above. For example, the result of adding the polynomials: P(x): 9x? 12 x3 2 and Q(x): 5x + 12x3 + 2x + 7 would be R(x): 5x +9x? + 2x + 5. This involves: Traversing P and Q, Doing sum of 'corresponding terms, Creation of new nodes Building list R, Returning pointer to R. 1. Have the user type-in the (coefficient, power) information for each of the terms. 2. Have a function to print the polynomial (given the head pointer) 3. Have a function to add two polynomials