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.