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();
    }
}
#include
#include

struct Node {
    int coeff;
    int pow;
    struct Node* next;
};
 
// Function to create new node
void create_node(int x, int y, struct Node** temp)
{
    struct Node *r, *z;
    z = *temp;
    if (z == NULL) {
        r = (struct Node*)malloc(sizeof(struct Node));
        r->coeff = x;
        r->pow = y;
        *temp = r;
        r->next = (struct Node*)malloc(sizeof(struct Node));
        r = r->next;
        r->next = NULL;
    }
    else {
        r->coeff = x;
        r->pow = y;
        r->next = (struct Node*)malloc(sizeof(struct Node));
        r = r->next;
        r->next = NULL;
    }
}
 
// Function Adding two polynomial numbers
void polyadd(struct Node* poly1, struct Node* poly2,
             struct Node* poly)
{
    while (poly1->next && poly2->next) {
        if (poly1->pow > poly2->pow) {
            poly->pow = poly1->pow;
            poly->coeff = poly1->coeff;
            poly1 = poly1->next;
        }
 
        else if (poly1->pow < poly2->pow) {
            poly->pow = poly2->pow;
            poly->coeff = poly2->coeff;
            poly2 = poly2->next;
        }
        else {
            poly->pow = poly1->pow;
            poly->coeff = poly1->coeff + poly2->coeff;
            poly1 = poly1->next;
            poly2 = poly2->next;
        }
 
        // Dynamically create new node
        poly->next
            = (struct Node*)malloc(sizeof(struct Node));
        poly = poly->next;
        poly->next = NULL;
    }
    while (poly1->next || poly2->next) {
        if (poly1->next) {
            poly->pow = poly1->pow;
            poly->coeff = poly1->coeff;
            poly1 = poly1->next;
        }
        if (poly2->next) {
            poly->pow = poly2->pow;
            poly->coeff = poly2->coeff;
            poly2 = poly2->next;
        }
        poly->next
            = (struct Node*)malloc(sizeof(struct Node));
        poly = poly->next;
        poly->next = NULL;
    }
}
 
// Display Linked list
void show(struct Node* node)
{
    while (node->next != NULL) {
        printf("%dx^%d", node->coeff, node->pow);
        node = node->next;
        if (node->coeff >= 0) {
            if (node->next != NULL)
                printf("+");
        }
    }
}
 
// Driver code
int main()
{
    struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL;
 
    // Create first list of 5x^2 + 4x^1 + 2x^0
    create_node(5, 2, &poly1);
    create_node(4, 1, &poly1);
    create_node(2, 0, &poly1);
 
    // Create second list of -5x^1 - 5x^0
    create_node(-5, 1, &poly2);
    create_node(-5, 0, &poly2);
 
    printf("1st Number: ");
    show(poly1);
 
    printf("\n2nd Number: ");
    show(poly2);
 
    poly = (struct Node*)malloc(sizeof(struct Node));
 
    // Function add two polynomial numbers
    polyadd(poly1, poly2, poly);
 
    // Display resultant List
    printf("\nAdded polynomial: ");
    show(poly);
 
    return 0;
}
class Node :
	def __init__(self, data, power) :
		self.data = data
		self.power = power
		self.next = None
	
	def updateRecord(self, data, power) :
		self.data = data
		self.power = power
	

class AddPolynomial :
	def __init__(self) :
		self.head = None
	
	def display(self) :
		if (self.head == None) :
			print("Empty Polynomial ")
		
		print(" ", end = "")
		temp = self.head
		while (temp != None) :
			if (temp != self.head) :
				print("+", temp.data, end = "")
			else :
				print(temp.data, end = "")
			
			if (temp.power != 0) :
				print("x^", temp.power, end = " ",sep = "")
			
			temp = temp.next
		
		print(end = "\n")
	
	def addNode(self, data, power) :
		if (self.head == None) :
			self.head = Node(data, power)
		else :
			node = None
			temp = self.head
			location = None
			while (temp != None and temp.power >= power) :
				location = temp
				temp = temp.next
			
			if (location != None and location.power == power) :
				location.data = location.data + data
			else :
				node = Node(data, power)
				if (location == None) :
					node.next = self.head
					self.head = node
				else :
					node.next = location.next
					location.next = node
				
			
		
	
	def addTwoPolynomials(self, other) :
		result = None
		tail = None
		node = None
		first = self.head
		second = other.head
		while (first != None or second != None) :
			node = Node(0, 0)
			if (result == None) :
				result = node
			
			if (first != None and second != None) :
				if (first.power == second.power) :
					node.updateRecord(first.data + second.data, first.power)
					first = first.next
					second = second.next
				elif (first.power > second.power) :
					node.updateRecord(first.data, first.power)
					first = first.next
				else :
					node.updateRecord(second.data, second.power)
					second = second.next
				
			elif (first != None) :
				node.updateRecord(first.data, first.power)
				first = first.next
			else :
				node.updateRecord(second.data, second.power)
				second = second.next
			
			if (tail == None) :
				tail = node
			else :
				tail.next = node
				tail = node
			
		
		return result
	

if __name__ == "__main__":
	poly1 = AddPolynomial()
	poly2 = AddPolynomial()
	result = AddPolynomial()
	poly1.addNode(5, 4)
	poly1.addNode(3, 2)
	poly1.addNode(1, 0)
	poly2.addNode(4, 4)
	poly2.addNode(2, 2)
	poly2.addNode(1, 1)
	print("\n Polynomial A")
	poly1.display()
	print(" Polynomial B")
	poly2.display()
	result.head = poly1.addTwoPolynomials(poly2)
	print(" Result")
	result.display()

Output

9x4 + 5x2+ 1x1 + 1x0

Note : Also xn is same as xn (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.
[forminator_quiz id="4123"]

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.

Leave a Reply

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