# Multiplication of two polynomials using Linked List ### Introduction

One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.

We are given two polynomials in the form of linked lists, and we need to create a new list containing the multiplicative product of the given polynomials.

### Problem Statement

We have been given two linked lists representing a polynomial each. Let say Poly1 and Poly2 are the given polynomials, so we need to multiply the polynomials and print the output.

### Problem Statement Understanding

Let’s try to understand the problem with the help of examples by referring the websites to learn programming.

Suppose the given linked lists are:
Poly1: 3x3 + 6x1 - 9
Poly2: 9x3 - 8x2 + 7x1 + 2

• Now, according to the problem statement, we need to multiply these polynomials Poly1 and Poly2.
• So we will multiply each term in Poly1 with every term in Poly2, and then we will add up all the term with the same power of x such that each term in the final resultant polynomial list has a different power of x.
##### Output

Resultant Polynomial: 27x6 - 24x5 + 75x4 - 123x3 + 114x2 - 51x1 - 18

#### Some other examples:

Input 1
Poly1: 6x1 - 9
Poly2: 7x1 + 2

Output 1
Resultant Polynomial: 42x2 - 51x1 - 18

Input 2
Poly1: 8x1 + 7
Poly2: 4x2 + 5

Output 2
Resultant Polynomial: 32x3 + 28x2 + 40x1 + 35

Now I think from the above examples the problem statement is clear. So, let's see in the next section see how we can approach it.

### Approach and Algorithm

1) First, we will traverse the Poly1 and multiply each of its nodes, with each and every node in Poly2.

• We will multiply the power of the nodes and store it in a variable power.
• We will multiply the coefficients of the nodes and store it in a variable coeff.
• Then we will add a new node in Poly3 with power and coeff values.
2) We will perform step 1 until each node in Poly1 has been multiplied with every node of Poly2.
3) After all the terms in the given polynomials are multiplied and stored in a new list Poly3, then we will combine the different terms with the same power.
• We will traverse the Poly3 to compare the power of each factor, starting with the next node.
• If the power is same for any factors, we will add the coefficients and remove the other duplicate node.
4) So now what we have is the required polynomial, and we can print the answer.

### Dry run

Let's dry run with an example:
Poly1: 3x^3 + 6x^1 - 9
Poly2: 9x^3 - 8x^2 + 7x^1 + 2

To multiply the above polynomials Poly1 and Poly2 we will have to perform the following operations:

• We have to multiply all the terms of Poly1 one by one with every term of Poly2, so first, we will multiply 3x3 with every other term in Poly2.(result: 27x6 - 24x5 + 21x4 + 6x3)
• Now we take 6x1 and multiply it with every other term in Poly2.(result: 27x6 - 24x5 + 21x4 + 6x3 + 54x4 - 48x3 + 42x2 + 12x1)
• Now we take -9 and multiply it with every other term in Poly2.(result: 27x6 - 24x5 + 21x4 + 6x3 + 54x4 - 48x3 + 42x2 + 12x1 - 81x3 + 72x2 - 63x1 - 18)
• We will remove all the duplicates, i.e., add the value of nodes with the same powers.
• So the final result: 27x6 - 24x5 + 75x4 - 123x3 + 114x2 - 51x1 - 18

You can take examples by yourself to get a better understanding of the problem.

### Code Implementation:

```#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
// Define useful field of Node
int data;
int power;
struct Node * next;
}Node;

Node * getNode(int data, int power)
{
// Create dynamic memory of Node
Node * ref = (Node * ) malloc(sizeof(Node));
if (ref == NULL)
{
// Failed to create memory
return NULL;
}
ref->data = data;
ref->power = power;
ref->next = NULL;
return ref;
}
// Update node value
void updateRecord(Node * ref, int data, int power)
{
ref->data = data;
ref->power = power;
}
typedef struct MultiplyPolynomial
{
// Define useful field of MultiplyPolynomial
}MultiplyPolynomial;

MultiplyPolynomial * getMultiplyPolynomial()
{
// Create dynamic memory of MultiplyPolynomial
MultiplyPolynomial * ref = (MultiplyPolynomial * )
malloc(sizeof(MultiplyPolynomial));
if (ref == NULL)
{
// Failed to create memory
return NULL;
}
return ref;
}
// Insert Node element
void insert(MultiplyPolynomial * ref, int data, int power)
{
{
}
else
{
Node * node = NULL;
Node * location = NULL;
// Find the valid new node location
while (temp != NULL && temp->power >= power)
{
location = temp;
temp = temp->next;
}
if (location != NULL && location->power == power)
{
// When polynomial power already exists
location->data = location->data + data;
}
else
{
node = getNode(data, power);
if (location == NULL)
{
// When add node in begining
}
else
{
// When adding node in intermediate
// location or end location
node->next = location->next;
location->next = node;
}
}
}
}
// Perform multiplication of given polynomial
MultiplyPolynomial * multiplyPolynomials(
MultiplyPolynomial * ref, MultiplyPolynomial * other)
{
// Define some useful variable
MultiplyPolynomial * result = getMultiplyPolynomial();
// Get first node of polynomial
int power_value = 0;
int coefficient = 0;
// Execute loop until when polynomial are exist
while (poly1 != NULL)
{
while (temp != NULL)
{
// Get result info
power_value = poly1->power + temp->power;
coefficient = poly1->data * temp->data;
insert(result, coefficient, power_value);
// Visit to next node
temp = temp->next;
}
// Visit to next node
poly1 = poly1->next;
}
// return first node
return result;
}
// Display given polynomial nodes
void display(MultiplyPolynomial * ref)
{
{
printf("Empty Polynomial ");
}
printf(" ");
while (temp != NULL)
{
{
printf(" + %d", temp->data);
}
else
{
printf("%d",temp->data);
}
if (temp->power != 0)
{
printf("x^%d", temp->power);
}
// Visit to next node
temp = temp->next;
}
printf("\n");
}
int main()
{
MultiplyPolynomial * a = getMultiplyPolynomial();
MultiplyPolynomial * b = getMultiplyPolynomial();
// Add node in polynomial A
insert(a, 9, 3);
insert(a, 4, 2);
insert(a, 3, 0);
insert(a, 7, 1);
insert(a, 3, 4);
// Add node in polynomial b
insert(b, 7, 3);
insert(b, 4, 0);
insert(b, 6, 1);
insert(b, 1, 2);
// Display Polynomial nodes
printf("\n Polynomial A\n");
display(a);
printf(" Polynomial B\n");
display(b);
MultiplyPolynomial * result = multiplyPolynomials(a, b);
// Display calculated result
printf(" Result\n");
display(result);
}

```
```import java.util.*;
class PrepBytes
{

static class Node {
int coeff, power;
Node next;
};

static Node addnode(Node start, int coeff, int power)
{
Node newnode = new Node();
newnode.coeff = coeff;
newnode.power = power;
newnode.next = null;

if (start == null)
return newnode;

Node ptr = start;
while (ptr.next != null)
ptr = ptr.next;
ptr.next = newnode;

return start;
}

static void printList( Node ptr)
{
while (ptr.next != null) {
System.out.print( ptr.coeff + "x^" + ptr.power + " + ");

ptr = ptr.next;
}
System.out.print( ptr.coeff  +"\n");
}

static void removeDuplicates(Node start)
{
Node ptr1, ptr2, dup;
ptr1 = start;

while (ptr1 != null && ptr1.next != null) {
ptr2 = ptr1;

while (ptr2.next != null) {

if (ptr1.power == ptr2.next.power) {

ptr1.coeff = ptr1.coeff + ptr2.next.coeff;
dup = ptr2.next;
ptr2.next = ptr2.next.next;

}
else
ptr2 = ptr2.next;
}
ptr1 = ptr1.next;
}
}

static Node multiply(Node poly1, Node poly2,
Node poly3)
{

Node ptr1, ptr2;
ptr1 = poly1;
ptr2 = poly2;
while (ptr1 != null) {
while (ptr2 != null) {
int coeff, power;

coeff = ptr1.coeff * ptr2.coeff;

power = ptr1.power + ptr2.power;

ptr2 = ptr2.next;
}

ptr2 = poly2;

ptr1 = ptr1.next;
}

removeDuplicates(poly3);
return poly3;
}

public static void main(String args[])
{

Node poly1 = null, poly2 = null, poly3 = null;

poly3 = multiply(poly1, poly2, poly3);

System.out.print( "Resultant Polynomial: ");
printList(poly3);
}

}
```
```class Node:
def __init__(self):
self.coeff = None
self.power = None
self.next = None

newnode = Node()
newnode.coeff = coeff
newnode.power = power
newnode.next = None

if (start == None):
return newnode

ptr = start
while (ptr.next != None):
ptr = ptr.next
ptr.next = newnode
return start

def printList(ptr):

while (ptr.next != None):
print(str(ptr.coeff) + 'x^' + str(ptr.power), end = '')
if( ptr.next != None and ptr.next.coeff >= 0):
print('+', end = '')
ptr = ptr.next
print(ptr.coeff)

def removeDuplicates(start):
ptr2 = None
dup = None
ptr1 = start

while (ptr1 != None and ptr1.next != None):
ptr2 = ptr1

while (ptr2.next != None):

if (ptr1.power == ptr2.next.power):

ptr1.coeff = ptr1.coeff + ptr2.next.coeff
dup = ptr2.next
ptr2.next = ptr2.next.next

else:
ptr2 = ptr2.next

ptr1 = ptr1.next

def multiply(poly1, Npoly2, poly3):

ptr1 = poly1
ptr2 = poly2

while (ptr1 != None):
while (ptr2 != None):

coeff = ptr1.coeff * ptr2.coeff
power = ptr1.power + ptr2.power
ptr2 = ptr2.next

ptr2 = poly2
ptr1 = ptr1.next

removeDuplicates(poly3)
return poly3

if __name__=='__main__':
poly1 = None
poly2 = None
poly3 = None

poly3 = multiply(poly1, poly2, poly3)

print("Resultant Polynomial:- ", end = '')
printList(poly3)

```

#### Output:

Resultant Polynomial: 18x3 + 54x2 + 76x1 + 48

Time Complexity: O(n*m), where n is the total number of nodes in the first polynomial and m is the number of nodes in the second polynomial.
Space complexity: O(n+m), we need to store all the multiplied values in the node.

So, in this blog, we have tried to explain how you can do Multiplication Of Two Polynomials Using Linked List. 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.

## One thought on “Multiplication of two polynomials using Linked List”

1. Deep Singsane says:

Hi Abhinav, you nicely created the program in this post but can I get the C program code for the same algorithm?