# 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

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(3×2) and b(2×2) 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

```#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

// Display resultant List
show(poly);

return 0;
}
```
```public class addingPolynomials {
static class Node {
int coefficient;
int degree;
Node next;

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

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;
}

}

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) {
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) {
tail2 = ptr;
}

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

i++;
}

Node head = sum;

while (head != null) {

if (head.next != null)
System.out.print(" + ");
}
System.out.println();
}
}
```
```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

def __init__(self) :

def display(self) :
if (self.head == None) :
print("Empty Polynomial ")

print(" ", end = "")
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
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) :
else :
node.next = location.next
location.next = node

def addTwoPolynomials(self, other) :
result = None
tail = None
node = None
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__":
print("\n Polynomial A")
poly1.display()
print(" Polynomial B")
poly2.display()
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.