Adding two polynomials using Linked List

Problem Statement

In this problem, we are given two polynomials represented by Linked Lists and are asked to add them.

Let's see an example:
Input : 5x4 + 3x2 + 1, 4x4 + 2x2 + x
Output : 9x4 + 5x2 + x + 1

Problem Statement Understanding

Let us try to understand the above example:
Given List1 = 5x4 + 3x2 + 1 and List2 = 4x4 + 2x2 + x

  • 5x4 and 4x4 are like terms, so we add their coefficients,
    Resultant list = 9x4
  • 3x2 and 2x2 are like terms, so we add their coefficients.
    Resultant list = 9x4 + 5x2
  • 1 and x are not like terms as x which is also x1 has a degree greater than 1 which is x0 so we append x to our resultant list.
    Resultant list = 9x4 + 5x2 + x
  • 1 is left, so we append 1 to our resultant list.
    Resultant list = 9x4 + 5x2 + x + 1

Helpful Observations

1) We only added the coefficients of the like terms (terms having the same variables and the same degree).
2) The terms are placed in descending order by degree.

So, we will use the above observations to design our algorithm.

Structure of node

The linked list node contains three values:

  • Coefficient: The numeric value.
  • Degree: The power of the variable x.
  • Address: The address of the next node of the linked list.

Approach

To add two polynomials that are represented as a linked list, we will add the coefficients of variables with the degree.

We will traverse both the list and at any step we will compare the degree of current nodes in both the list:

  • we will add their coefficients if their degree is same and append to the resultant list .
  • Otherwise we will append the node with greater node in the resultant list.

Algorithm

  • Create a new linked list, newHead to store the resultant list.
  • Traverse both lists until one of them is null.
  • If any list is null insert the remaining node of another list in the resultant list.
  • Otherwise compare the degree of both nodes, a (first list’s node) and b (second list’s node). Here three cases are possible:
    1) If the degree of a and b is equal, we insert a new node in the resultant list with the coefficient equal to the sum of coefficients of a and b and the same degree.
    2) If the degree of a is greater than b, we insert a new node in the resultant list with the coefficient and degree equal to that of a.
    3) If the degree of b is greater than a, we insert a new node in the resultant list with the coefficient and degree equal to that of b.

Dry run

Let the linked lists are:
List1 = 5x4 + 3x2 + 1
List2 = 4x4 + 2x2 + x

Note: For better understanding follow the code along with dry run.

  • First of all, we will initialize the resultant list which will contain the addition of the two given input polynomial in form of a linked list (Node newHead = new Node(0, 0)).
  • We will create three-pointers a, b and c and will make pointer a point to the head of the List1, pointer b point to the head of the List2 and pointer c point to the head of the resultant list newHead.
  • As a(5x4) and b(4x4) are not null, so we enter the while loop (where a(5x4) means that pointer a is pointing to 5x4 in List1 and similarly b(4x4) means that pointer b is pointing to 4x4 in List2).
  • As a.degree is equal to b.degree so c.next will be a + b i.e, 9x4.
  • Move a, b and c to their next pointers.
  • Now, as a(3x2) and b(2x2) are still not null so we will be still in the while loop.
  • As a.degree is still equal to b.degree so c.next will be a + b i.e, 5x2.
  • Again move a, b and c to their next pointers.
  • a(1) and b(x) are still not null so we will be still in the while loop.
  • As now a.degree is less than b.degree so c.next will point to the one with a higher degree, which is b(x).
  • Again move b and c to their next pointers.
  • But as now b is null so make the next of c point to a(1).
  • Again move a and c to their next pointers.
  • As now a and b both are null so we will exit the while loop.

Finally when we exit the while loop, newHead.next will contain the addition of the two given input polynomial in form of a linked list.

Code Implementation

public class addingPolynomials {
    static class Node {
        int coefficient;
        int degree;
        Node next;

        Node(int c, int d) {
            coefficient = c;
            degree = d;
        }
    }

    public static Node add(Node head1, Node head2) {
        Node newHead = new Node(0, 0);
        Node a = head1;
        Node b = head2;
        Node c = newHead;

        while (a != null || b != null) {

            if (a == null) {
                c.next = b;
                break;
            } 
            else if (b == null) {
                c.next = a;
                break;
            }

            else if (a.degree == b.degree) {
                c.next = new Node(a.coefficient + b.coefficient, a.degree);

                a = a.next;
                b = b.next;
            }

            else if (a.degree > b.degree) {
                c.next = new Node(a.coefficient, a.degree);

                a = a.next;
            }

            else if ((a.degree < b.degree)) {
                c.next = new Node(b.coefficient, b.degree);

                b = b.next;
            }

            c = c.next;
        }

        return newHead.next;
    }

    public static void main(String[] args) {

        Node head1 = null;
        Node head2 = null;

        Node tail1 = null;
        Node tail2 = null;

        // First polynomial data
        int coeff_of_p1[] = { 5, 3, 1 };
        int degree_of_p1[] = { 4, 2, 0 };
        int len1 = coeff_of_p1.length;

        // Creating first polynomial
        int i = 0;
        while (len1-- > 0) {
            int c = coeff_of_p1[i];
            int d = degree_of_p1[i];

            Node ptr = new Node(c, d);

            if (head1 == null) {
                head1 = ptr;
                tail1 = ptr;
            }

            else {
                tail1.next = ptr;
                tail1 = ptr;
            }

            i++;
        }

        // Second polynomial data
        int coeff_of_p2[] = { 4, 2, 1 };
        int degree_of_p2[] = { 4, 2, 1 };
        int len2 = coeff_of_p2.length;

        // Creating second polynomial
        i = 0;
        while (len2-- > 0) {
            int c = coeff_of_p2[i];
            int d = degree_of_p2[i];

            Node ptr = new Node(c, d);

            if (head2 == null) {
                head2 = ptr;
                tail2 = ptr;
            }

            else {
                tail2.next = ptr;
                tail2 = ptr;
            }

            i++;
        }

        Node sum = add(head1, head2);
        Node head = sum;

        while (head != null) {
            System.out.print(head.coefficient + "x^" + head.degree);

            if (head.next != null)
                System.out.print(" + ");
            head = head.next;
        }
        System.out.println();
    }
}

Output

9x^4 + 5x^2 + 1x^1 + 1x^0

Note : Also xn is same as x^n (both represent same thing x raise to power n).

Time Complexity: O(n + m), where n is the length of the first list and m is the length of the second list.

So, in this blog, we have tried to explain how you can add two polynomials represented as linked lists. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Program to convert ArrayList to LinkedList in Java
Next post LinkedList listiterator() method in Java

Leave a Reply

Your email address will not be published. Required fields are marked *