This program is worth 40 pts extra credit.
The outline of a polynomial class is shown below. Polynomials are to be stored as linked lists of terms, where each term has a coefficient and an exponent. The terms are in increasing order of exponent. Terms with coefficients of 0 are omitted from the list. (The 0 polynomial is represented by head = null.)
Write the methods that are missing. You may include other private methods that facilitate writing the public methods.
The constructor with no arguments creates a zero polynomial.
The other constructor takes a two dimensional array like this: {{3, 0}, {2, 1}, {-5, 3}, {4,7}} where the item {a, b} represents a term with cofficient a and exponent b. So this example represents the polynomial 3 + 2x - 5x^3 + 4x^7.
The add and substract methods use a modification of the merge algorithm.
You might find it advantageous to write private methods that take Term arguments (the heads of the lists) and return a Term (the head of the new list). Add and substract can be done recursively. It might be easier. It is definitely easier to do multiplication recursively.
The toString method will return a string representation of a polynomial. It should return a string like "3 + 2x - 5x^3 + 4x^7". In particular, the constant term should only display the coefficient, without "x^0". The linear term should only display the coefficient followed by "x"; not "x^1". Terms with negative coefficients should be display as shown above; not "+ -5x^3", except for the constant term.
Make sure the arithmetic methods omit any terms with a 0 coefficient, do not contain any terms with duplicate exponents, and put terms in increasing order of coefficient.
I will run my own test program that uses your toString method, so make sure it works.