Addition of two polynomials using circular linked list in python

Adding two polynomials using Circular Linked List

Given two polynomial numbers represented by a circular linked list, the task is to add these two polynomials by adding the coefficients of the powers of the same variable.

Table of Contents Show

Adding two polynomials using Circular Linked List
Adding two polynomials using Linked List
Polynomial Addition using Circular Header Linked List
Program to add two polynomials given as linked lists using Python

Note: In given polynomials, the term containing the higher power of x will come first.

Examples:

Input:
1st Number = 5x^2 * y^1 + 4x^1 * y^2 + 3x^1 * y^1 + 2x^1
2nd Number = 3x^1 * y^2 + 4x^1
Output:
5x^2 * y^1 + 7x^1 * y^2 + 3x^1 * y^1 + 6x^1
Explanation:
The coefficient of x^2 * y^1 in 1st numbers is 5 and 0 in the 2nd number. Therefore, sum of the coefficient of x^2 * Y^1 is 5.
The coefficient of x^1 * y^2 in 1st numbers is 4 and 3 in the 2nd number. Therefore, sum of the coefficient of x^1 * Y^2 is 7.
The coefficient of x^1 * y^1 in 1st numbers is 3 and 0 in the 2nd number. Therefore, sum of the coefficient of x^1 * Y^1 is 2.
The coefficient of x^1 * Y^0 in 1st numbers is 2 and 4 in the 2nd number. Therefore, sum of the coefficient of x^1 * Y^0 is 6.

Input:
1st Number = 3x^3 * y^2 + 2x^2 + 5x^1 * y^1 + 9y^1 + 2
2nd Number = 4x^3 * y^3 + 2x^3 * y^2 + 1y^2 + 3
Output:
4x^3 * y^3 + 5x^3 * y^2 + 2x^2 + 5x^1 * y^1 + 1y^2 + 9y^1 + 5

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: Follow the below steps to solve the problem:

Create two circular linked lists, where each node will consist of the coefficient, power of x, power of y and pointer to the next node.
Traverse both the polynomials and check the following conditions:
- If power of x of 1st polynomial is greater than power of x of second polynomial then store node of first polynomial in resultant polynomial and increase counter of polynomial 1.
- If power of x of 1st polynomial is less than power of x of second polynomial then store the node of second polynomial in resultant polynomial and increase counter of polynomial 2.
- If power of x of 1st polynomial is equal to power of x of second polynomial and power of y of 1st polynomial is greater than power of y of 2nd polynomial then store the node of first polynomial in resultant polynomial and increase counter of polynomial 1.
- If power of x of 1st polynomial is equal to power of x of second polynomial and power of y of 1st polynomial is equal to power of y of 2nd polynomial then store the sum of coefficient of both polynomial in resultant polynomial and increase counter of both polynomial 1 and polynomial 2.
If there are nodes left to be traversed in 1st polynomial or in 2nd polynomial then append them in resultant polynomial.
Finally, print the resultant polynomial.

Below is the implementation of the above approach:

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>

using namespace std;
// Structure of a node
// in a circular linked list

struct Node {

// Stores coefficient

// of a node

int coeff;

// Stores power of'

// variable x of a node

int powx;

// Stores power of

// variable y of a node

int powy;

// Stores pointer

// to next node

struct Node* next;
};
// Function to dynamically create a node

void create_node(int c, int p1, int p2,

struct Node** temp)
{

// Stores new node

struct Node *r;

// Stores temp node

struct Node *z

= *temp;

// Dynamically create a new node

r = (struct Node*)malloc(

sizeof(struct Node));

// Update coefficient

// of r

r->coeff = c;

// Update power of

// variable x in r

r->powx = p1;

// Update power of

// variable y in r

r->powy = p2;

// If z is null

if (z == NULL) {

// Update temp node

(*temp) = r;

// Update next pointer

// of temp node

(*temp)->next = (*temp);

}

else {

// Update next pointer

// of z

r->next = z->next;

// Update next pointer

// of z

z->next = r;

// Update temp Node

(*temp) = r;

}
}
// Function to add polynomial of two list

void add_poly(struct Node* poly1,

struct Node* poly2, struct Node** temp)
{

// Stores head node of polynomial1

struct Node *start1 = poly1;

// Stores head node of polynomial1

struct Node *start2 = poly2;

// Update poly1

poly1 = poly1->next;

// Update poly2

poly2 = poly2->next;

// Traverse both circular linked list

while ((poly1 != start1 &&

poly2 != start2)) {

// Stores new node

struct Node* r;

// Stores temp node

struct Node* z

= *temp;

// Dynamically create a new node

r = (struct Node*)malloc(

sizeof(struct Node));

// Update coefficient of r

r->coeff = 0;

// If power of x of poly1 is

// greater than power of x of poly2

if (poly1->powx > poly2->powx) {

// Update coefficient of r

r->coeff = poly1->coeff;

// Update of power of x in r

r->powx = poly1->powx;

// Update of power of y in r

r->powy = poly1->powy;

// Update poly1

poly1 = poly1->next;

}

// If power of x of 1st polynomial is

// less than power of x of 2nd poly

else if (poly1->powx < poly2->powx) {

// Update coefficient OF r

r->coeff = poly2->coeff;

// Update power of x in r

r->powx = poly2->powx;

// Update power of y in r

r->powy = poly2->powy;

// Update ploy2

poly2 = poly2->next;

}

// If power of x of 1st polynomial is

// equal to power of x of 2nd poly

else {

// Power of y of 1st polynomial is

// greater than power of y of poly2

if (poly1->powy > poly2->powy) {

// Update coefficient of r

r->coeff = poly1->coeff;

// Update power of x in r

r->powx = poly1->powx;

// Update power of y in r

r->powy = poly1->powy;

// Update poly1

poly1 = poly1->next;

}

// If power of y of poly1 is

// less than power of y of ploy2

else if (poly1->powy <

poly2->powy) {

// Update coefficient of r

r->coeff = poly2->coeff;

// Update power of x in r

r->powx = poly2->powx;

// Update power of y in r

r->powy = poly2->powy;

// Update poly2

poly2 = poly2->next;

}

// If power of y of 1st poly is

// equal to power of y of ploy2

else {

// Update coefficient of r

r->coeff = poly2->coeff

+ poly1->coeff;

// Update power of x in r

r->powx = poly1->powx;

// Update power of y in r

r->powy = poly1->powy;

// Update poly1

poly1 = poly1->next;

// Update poly2

poly2 = poly2->next;

}

}

// If z is null

if (z == NULL) {

// Update temp

(*temp) = r;

// Update next pointer

// of temp

(*temp)->next = (*temp);

}

else {

// Update next pointer

// of r

r->next = z->next;

// Update next pointer

// of z

z->next = r;

// Update temp

(*temp) = r;

}

}

// If there are nodes left to be

// traversed in poly1 or poly2 then

// append them in resultant polynomial .

while (poly1 != start1 ||

poly2 != start2) {

// If poly1 is not empty

if (poly1 != start1) {

// Stores new node

struct Node *r;

// Stores temp node

struct Node *z = *temp;

// Create new node

r = (struct Node*)malloc(

sizeof(struct Node));

// Update coefficient or r

r->coeff = poly1->coeff;

// Update power of x in r

r->powx = poly1->powx;

// Update power of y in r

r->powy = poly1->powy;

// Update poly1

poly1 = poly1->next;

// If z is null

if (z == NULL) {

// Update temp

(*temp) = r;

// Update pointer

// to next node

(*temp)->next = (*temp);

}

else {

// Update next pointer

// of r

r->next = z->next;

// Update next pointer of z

z->next = r;

// Update temp

(*temp) = r;

}

}

// If poly2 is not empty

if (poly2 != start2) {

// Stores new node

struct Node *r;

// Stores temp node

struct Node *z = *temp;

// Create new node

r = (struct Node*)malloc(

sizeof(struct Node));

// Update coefficient of z

z->coeff = poly2->coeff;

// Update power of x in z

z->powx = poly2->powx;

// Update power of y in z

z->powy = poly2->powy;

// Update poly2

poly2 = poly2->next;

// If z is null

if (z == NULL) {

// Update temp

(*temp) = r;

// Update next pointer

// of temp

(*temp)->next = (*temp);

}

else {

// Update next pointer

// of r

r->next = z->next;

// Update next pointer

// of z

z->next = r;

// Update temp

(*temp) = r;

}

}

}

// Stores new node

struct Node *r;

// Stores temp node

struct Node *z = *temp;

// Create new node

r = (struct Node*)malloc(

sizeof(struct Node));

// Update coefficient of r

r->coeff = 0;

// If power of x of start1 greater than

// power of x of start2

if (start1->powx > start2->powx) {

// Update coefficient of r

r->coeff = start1->coeff;

// Update power of x in r

r->powx = start1->powx;

// Update power of y in r

r->powy = start1->powy;

}

// If power of x of start1 less than

// power of x of start2

else if (start1->powx < start2->powx) {

// Update coefficient of r

r->coeff = start2->coeff;

// Update power of x in r

r->powx = start2->powx;

// Update power of y in r

r->powy = start2->powy;

}

// If power of x of start1 equal to

// power of x of start2

else {

// If power of y of start1 greater than

// power of y of start2

if (start1->powy > start2->powy) {

// Update coefficient of r

r->coeff = start1->coeff;

// Update power of x in r

r->powx = start1->powx;

// Update power of y in r

r->powy = start1->powy;

}

// If power of y of start1 less than

// power of y of start2

else if (start1->powy <

start2->powy) {

// Update coefficient of r

r->coeff = start2->coeff;

// Update power of x in r

r->powx = start2->powx;

// Update power of y in r

r->powy = poly2->powy;

}

// If power of y of start1 equal to

// power of y of start2

else {

// Update coefficient of r

r->coeff = start2->coeff

+ start1->coeff;

// Update power of x in r

r->powx = start1->powx;

// Update power of y in r

r->powy = start1->powy;

}

}

// If z is null

if (z == NULL) {

// Update temp

(*temp) = r;

// Update next pointer

// of temp

(*temp)->next = (*temp);

}

else {

// Update next pointer of r

r->next = z->next;

// Update next pointer of z

z->next = r;

// Update temp

(*temp) = r;

}
}
// Display the circular linked list

void display(struct Node* node)
{

// Stores head node of list

struct Node* start = node;

// Update node

node = node->next;

// Traverse the list

while (node != start &&

node->coeff != 0) {

// Print coefficient of

// current node

cout << node->coeff;

// If power of variable x

// is not zero

if (node->powx != 0)

cout << "x^" << node->powx;

// If power of variable x

// and y is not zero

if(node->powx != 0 &&

node->powy != 0)

cout<<" * ";

// If power of variable y

// is not zero

if (node->powy != 0)

cout << "y^" << node->powy;

// Add next term of

// the polynomial

if (node != start &&

node->next->coeff != 0) {

cout << " + ";

}

// Update node

node = node->next;

}

// Print coefficient of

// current node

cout << node->coeff;

// If power of variable x

// is not zero

if (node->powx != 0)

cout << "x^" << node->powx;

// If power of variable y

// is not zero

if (node->powy != 0)

cout << "y^" << node->powy;

cout << "\n\n";
}
// Driver Code

int main()
{

// Stores node of

// first polynomial

struct Node *poly1 = NULL;

// Stores node of

// second polynomial

struct Node *poly2 = NULL;

// Stores node of resultant

// polynomial

struct Node *store = NULL;

// Create first polynomial

create_node(5, 2, 1, &poly1);

create_node(4, 1, 2, &poly1);

create_node(3, 1, 1, &poly1);

create_node(2, 1, 0, &poly1);

create_node(3, 0, 1, &poly1);

create_node(2, 0, 0, &poly1);

// Create second polynomial

create_node(3, 1, 2, &poly2);

create_node(4, 1, 0, &poly2);

create_node(2, 0, 1, &poly2);

create_node(6, 0, 0, &poly2);

// Function call to add

// two polynomial

add_poly(poly1, poly2, &store);

// Display polynomial 1

cout << "Polynomial 1"

<< "\n";

display(poly1);

// Display polynomial 2

cout << "Polynomial 2"

<< "\n";

display(poly2);

// Display final addition of 2-variable polynomial

cout << "Polynomial after addition"

<< "\n";

display(store);

return 0;
}

Output Polynomial 1 5x^2 * y^1 + 4x^1 * y^2 + 3x^1 * y^1 + 2x^1 + 3y^1 + 2 Polynomial 2 3x^1 * y^2 + 4x^1 + 2y^1 + 6 Polynomial after addition 5x^2 * y^1 + 7x^1 * y^2 + 3x^1 * y^1 + 6x^1 + 5y^1 + 8

Time Complexity: O(M + N), where M and N are number of nodes in the first and second lists respectively.
Auxiliary Space: O(M + N)

Article Tags :

Linked List

Mathematical

circular linked list

Linked-List-Polynomial

maths-polynomial

Practice Tags :

Linked List

Mathematical

circular linked list

Read Full Article

Adding two polynomials using Linked List

Given two polynomial numbers represented by a linked list. Write a function that add these lists means add the coefficients who have same variable powers.
Example:

Input: 1st number = 5x2 + 4x1 + 2x0 2nd number = -5x1 - 5x0 Output: 5x2-1x1-3x0 Input: 1st number = 5x3 + 4x2 + 2x0 2nd number = 5x^1 - 5x^0 Output: 5x3 + 4x2 + 5x1 - 3x0

Polynomial Addition using Circular Header Linked List

#include<stdio.h>

#include<stdlib.h>

struct node

{

int coeff;

int expon;

struct node *link;

};

typedef struct node *NODE;

NODE getnode()

{

NODE x;

x = (NODE) malloc(sizeof(struct node));

return x;

}

NODEattach(int coeff, int expon, NODE head)

{

NODE temp, cur;

temp = getnode();

temp->coeff = coeff;

temp->expon = expon;

cur = head->link;

while(cur->link != head)

{

cur = cur->link;

}

cur->link = temp;

temp->link = head;

return head;

}

NODE read_poly(NODE head)

{

int i = 1, coeff, expon;

printf("\nEnter the coefficient as -999 to end the polynomial ");

while(1)

{

printf("\nEnter the %d term:\n",i++);

printf("\n\tCoeff = ");

scanf("%d", &coeff);

if(coeff == -999)

break;

printf("\n\tPow x = ");

scanf("%d", &expon);

head = attach(coeff, expon, head);

}

return head;

}

NODEpoly_add(NODE head1, NODE head2, NODE head3)

{

NODE a,b;

int coeff;

a = head1->link;

b = head2->link;

while(a != head1 && b != head2)

{

if(a->expon == b->expon)

{

coeff = a->coeff + b->coeff;

if(coeff != 0)

head3 = attach(coeff, a->expon, head3);

a = a->link;

b = b->link;

}

else if(a->expon > b->expon)

{

head3 = attach(a->coeff, a->expon, head3);

a = a->link;

}

else

{

head3 = attach(b->coeff, b->expon, head3);

b = b->link;

}

while(a != head1)

{

head3 = attach(a->coeff, a->expon, head3);

a = a->link;

}

while(b != head2)

{

head3 = attach(b->coeff, b->expon, head3);

b = b->link;

}

return head3;

}

voiddisplay(NODE head)

{

NODE temp;

if(head->link == head)

{

printf("\nPolynomial does not exist");

return;

}

temp = head->link;

while(temp != head)

{

printf("%dx^%d",temp->coeff, temp->expon);

temp = temp->link;

if(temp != head)

printf(" + ");

}

void main()

{

NODE head1, head2, head3;

head1 = getnode();

head2 = getnode();

head3 = getnode();

head1->link=head1;

head2->link=head2;

head3->link=head3;

printf("\nEnter the first polynomial \n");

head1 = read_poly(head1);

printf("\nEnter the second polynomial \n");

head2 = read_poly(head2);

head3 = poly_add(head1, head2, head3);

printf("\nPolynomial 1:\t");

display(head1);

printf("\nPolynomial 2:\t");

display(head2);

printf("\nPolynomial Result:\t");

display(head3);

}

Output:

Enter the first polynomial

Enter the coefficient as -999 to end the polynomial

Enter the 1 term:

Coeff = 1

Pow x = 3

Enter the 2 term:

Coeff = 1

Pow x = 2

Enter the 3 term:

Coeff = 1

Pow x = 1

Enter the 4 term:

Coeff = 1

Pow x = 0

Enter the 5 term:

Coeff = -999

Enter the second polynomial

Enter the coefficient as -999 to end the polynomial

Enter the 1 term:

Coeff = 7

Pow x = 2

Enter the 2 term:

Coeff = 5

Pow x = 1

Enter the 4 term:

Coeff = -999

Polynomial 1: 1x^3 + 1x^2 + 1x^1 + 1x^0

Polynomial 2: 7x^2 + 5x^1

Polynomial Result: 1x^3 + 8x^2 + 6x^1 + 1x^0

Program to add two polynomials given as linked lists using Python

PythonServer Side ProgrammingProgramming

Suppose, we are given two polynomials and we have to find out the addition of the two polynomials. The polynomials have to be represented as linked lists; the terms of the polynomials will be represented as a linked list node. Each linked list node will contain the coefficient value, power value, and the pointer to the next linked list node. We have to return a third linked list which is the addition of two linked list polynomials.

So, if the input is like

1x^1 + 1x^2 = 0 and 2x^1 + 3x^0 = 0,

then the output will be 3x^1 + 1x^2 + 3x^0 = 0

To solve this, we will follow these steps −

dummy := a new polynomial node
node := a new polynomial node
while poly1 and poly2 is not empty, do
- if power of poly1 > power of poly2, then
  - next of node := poly1
  - node := poly1
  - poly1 := next of poly1
- otherwise when power of poly1 < power of poly2, then
  - next of node := poly2
  - node := poly2
  - poly2 := next of poly2
- otherwise,
  - coef := coefficient of poly1 + coefficient of poly2
  - if coef is non-zero, then
    - poly1 := next of poly1
    - poly2 := next of poly2
next of node := poly1 or poly2
return next of dummy