Algebraic expressions composed of variables and coefficients connected by addition, subtraction, and multiplication are called polynomials. To represent polynomials using linked lists, one must construct nodes for each term, each of which has an exponent and a coefficient. To create a new polynomial, join two linked lists representing the polynomials by combining terms with the same exponent.

Example 1

Input: Polynomial 1 = 5x^2 + 4x^1

Polynomial 2 = 5x^2 + 2x^1

Output: sum = 10x^2 + 6x^1

Explanation: Adding 5x^2 + 4x^1 with 5x^2 + 2x^1 we get 10x^2 + 6x^1 as the result.

Example

Input: Polynomial 1 = 2x^2 + 4x^1

`Polynomial 2 = 3x^2 + 2x^1`

Output: sum = 5x^2 + 6x^1

Explanation: Adding 2x^2 + 4x^1 with 3x^2 + 2x^1 we get 5x^2 + 6x^1 as the result.

Example 3

Input: Polynomial 1 = 5x^2 + 4x^1 + 2x^0

`Polynomial 2 = 5x^1 + 5x^0`

Output: sum = 5x^2 + 9x^1 + 7x^0

Explanation: The polynomials are combined term-by-term, resulting in the polynomial 5x^2 + 9x^1 + 7x^0 by adding coefficients of terms with the same exponent.

Example 4

Input: Polynomial 1 = 3x^3 + 4x^2 + 5x^1

`Polynomial 2 = 2x^2 + 6x^1 + 7x^0`

Output: sum = 3x^3 + 6x^2 + 11^1 + 7x^0

Explanation: The polynomials are combined term-by-term, resulting in the polynomial 3x^3 + 6x^2 + 11^1 + 7x^0 by adding coefficients of terms with the same exponent.

## Approach 1: Using Iterative Approach

An iterative method is used to add two polynomials represented as linked lists. Each node in the linked list contains a coefficient and an exponent, and the polynomials are merged by summing coefficients of nodes with the same exponent. The algorithm traverses both linked lists, compares exponents, and creates a new linked list for the resultant polynomial.

### Algorithm

Step 1: Initialize pointers for the heads of both input polynomials and a result polynomial.

Step 2: Traverse both linked lists simultaneously:

Step 2.1: If exponents are equal, sum the coefficients and move both pointers forward.

Step 2.2: If one exponent is greater, add that term to the result and move the corresponding pointer forward.

Step 3: If one list is exhausted, append the remaining terms of the other list to the result.

Step 4: Return the resultant polynomial.

FileName: Polynomial.java

`class PolynomialNode {    int coefficient;    int exponent;    PolynomialNode next;    public PolynomialNode(int coefficient, int exponent) {        this.coefficient = coefficient;        this.exponent = exponent;        this.next = null;    }}public class Polynomial {    PolynomialNode head;    // Method to add two polynomials    public static Polynomial addPolynomials(Polynomial poly1, Polynomial poly2) {        PolynomialNode p1 = poly1.head; // Pointer for first polynomial        PolynomialNode p2 = poly2.head; // Pointer for second polynomial        Polynomial result = new Polynomial(); // Resultant polynomial        PolynomialNode p3 = null; // Pointer for resultant polynomial        // Traverse both polynomials simultaneously        while (p1 != null && p2 != null) {            int coeff, exp;            if (p1.exponent == p2.exponent) {                // If exponents are equal, sum the coefficients                coeff = p1.coefficient + p2.coefficient;                exp = p1.exponent;                p1 = p1.next;                p2 = p2.next;            } else if (p1.exponent > p2.exponent) {                // If p1's exponent is greater, take p1's term                coeff = p1.coefficient;                exp = p1.exponent;                p1 = p1.next;            } else {                // If p2's exponent is greater, take p2's term                coeff = p2.coefficient;                exp = p2.exponent;                p2 = p2.next;            }            // Create a new node for the result polynomial            PolynomialNode newNode = new PolynomialNode(coeff, exp);            if (result.head == null) {                result.head = newNode;                p3 = newNode;            } else {                p3.next = newNode;                p3 = newNode;            }        }        // If p1 has remaining terms, add them to the result        while (p1 != null) {            PolynomialNode newNode = new PolynomialNode(p1.coefficient, p1.exponent);            if (result.head == null) {                result.head = newNode;                p3 = newNode;            } else {                p3.next = newNode;                p3 = newNode;            }            p1 = p1.next;        }        // If p2 has remaining terms, add them to the result        while (p2 != null) {            PolynomialNode newNode = new PolynomialNode(p2.coefficient, p2.exponent);            if (result.head == null) {                result.head = newNode;                p3 = newNode;            } else {                p3.next = newNode;                p3 = newNode;            }            p2 = p2.next;        }        return result;    }    // Method to print the polynomial    public void printPolynomial() {        PolynomialNode temp = head;        while (temp != null) {            System.out.print(temp.coefficient + "x^" + temp.exponent);            if (temp.next != null) {                System.out.print(" + ");            }            temp = temp.next;        }        System.out.println();    }    public static void main (String[] args) {        Polynomial poly1 = new Polynomial();        poly1.head = new PolynomialNode(5, 2); // 5x^2        poly1.head.next = new PolynomialNode(4, 1); // + 4x^1        poly1.head.next.next = new PolynomialNode(2, 0); // + 2x^0        Polynomial poly2 = new Polynomial();        poly2.head = new PolynomialNode(5, 1); // 5x^1        poly2.head.next = new PolynomialNode(5, 0); // + 5x^0        System.out.print("Polynomial 1: ");        poly1.printPolynomial();        System.out.print("Polynomial 2: ");        poly2.printPolynomial();        Polynomial result = addPolynomials(poly1, poly2);        System.out.print("Sum: ");        result.printPolynomial();  //print the sum of the polynomial    }}`

Output

`Polynomial 1: 5x^2 + 4x^1 + 2x^0Polynomial 2: 5x^1 + 5x^0Sum: 5x^2 + 9x^1 + 7x^0`

Time Complexity: The time complexity of an algorithm is O(m+n), where m and n are the lengths of the two input polynomials. This is because each node in both linked lists is processed exactly once.

Space Complexity: The space complexity of an algorithm is O(m+n), for storing the resultant polynomial, as it contains nodes equal to the sum of the nodes in the input polynomials.

## Approach 2: Using Recursive Approach

A recursive method is used to add two polynomials represented as linked lists. Each node in the linked list contains a coefficient and an exponent. The polynomials are combined by recursively summing coefficients of nodes with the same exponent and moving to the next nodes.

### Algorithm

Step 1: Define a recursive function that takes two polynomial nodes as input.

Step 2: If both nodes are null, return null.

Step 3: If only one node is null, return the other node.

Step 4: Compare the exponents of the nodes:

Step 4.1: If exponents are equal, sum the coefficients and recurse for the next nodes.

Step 4.2: If one exponent is greater, retain that node and recurse for the next node of the smaller exponent polynomial.

Step 5: Create a new node with the combined coefficient and exponent and set its next to the result of the recursive call.

Step 6: Return the resultant polynomial node.

FileName: PolynomialRecursive.java

`class PolynomialNode {    int coefficient;    int exponent;    PolynomialNode next;    public PolynomialNode(int coefficient, int exponent) {        this.coefficient = coefficient;        this.exponent = exponent;        this.next = null;    }}public class PolynomialRecursive {    PolynomialNode head;    // Recursive method to add two polynomials    public static PolynomialNode addPolynomialsRecursive(PolynomialNode p1, PolynomialNode p2) {        if (p1 == null) return p2; // If first polynomial is empty, return second polynomial        if (p2 == null) return p1; // If second polynomial is empty, return first polynomial        PolynomialNode result;        if (p1.exponent == p2.exponent) {            // If exponents are equal, sum the coefficients            result = new PolynomialNode(p1.coefficient + p2.coefficient, p1.exponent);            result.next = addPolynomialsRecursive(p1.next, p2.next);        } else if (p1.exponent > p2.exponent) {            // If p1's exponent is greater, take p1's term            result = new PolynomialNode(p1.coefficient, p1.exponent);            result.next = addPolynomialsRecursive(p1.next, p2);        } else {            // If p2's exponent is greater, take p2's term            result = new PolynomialNode(p2.coefficient, p2.exponent);            result.next = addPolynomialsRecursive(p1, p2.next);        }        return result;    }    // Method to print the polynomial    public void printPolynomial() {        PolynomialNode temp = head;        while (temp != null) {            System.out.print(temp.coefficient + "x^" + temp.exponent);            if (temp.next != null) {                System.out.print(" + ");            }            temp = temp.next;        }        System.out.println();    }    public static void main (String[] args) {        PolynomialRecursive poly1 = new PolynomialRecursive();        poly1.head = new PolynomialNode(5, 2); // 5x^2        poly1.head.next = new PolynomialNode(4, 1); // + 4x^1        poly1.head.next.next = new PolynomialNode(2, 0); // + 2x^0        PolynomialRecursive poly2 = new PolynomialRecursive();        poly2.head = new PolynomialNode(5, 1); // 5x^1        poly2.head.next = new PolynomialNode(5, 0); // + 5x^0        System.out.print("Polynomial 1: ");        poly1.printPolynomial();        System.out.print("Polynomial 2: ");        poly2.printPolynomial();        PolynomialRecursive result = new PolynomialRecursive();        result.head = addPolynomialsRecursive(poly1.head, poly2.head);        System.out.print("Sum: ");        result.printPolynomial();  // print the sum of the polynomial    }}`

Output

`Polynomial 1: 5x^2 + 4x^1 + 2x^0Polynomial 2: 5x^1 + 5x^0Sum: 5x^2 + 9x^1 + 7x^0`

Time Complexity: The time complexity of an algorithm is O(m+n), where m and n are the lengths of the two input polynomials. This is because each node in both linked lists is processed exactly once.

Space Complexity: The space complexity of an algorithm is O(m+n), where m and n are the lengths of the two input polynomials. This is because of the recursive call stack.