InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
Given two polynomial expressions represented by linked lists. You need to write a function that adds these lists, that is, adds the coefficients that have the same variable powers. |
|
Answer» Implementation: struct NODE { int coefficient; int power; struct Node* next;};void createNode(int X, int y, struct Node** t){ struct Node *v, *z; z = *t; if (z == NULL) { v = NEW Node; v->coefficient = x; v->power = y; *t = v; v->next = new Node; v = v->next; v->next = NULL; } else { v->coefficient = x; v->power = y; v->next = new Node; v = v->next; v->next = NULL; }}// Function to add two polynomial expressionsvoid polyAdd(struct Node* poly1, struct Node* poly2, struct Node* poly){ while (poly1->next && poly2->next) { // If the power of the 1st polynomial is greater than that of 2nd, // then store 1st as it is and move its pointer if (poly2->power < poly1->power) { poly->power = poly1->power; poly->coefficient = poly1->coefficient; poly1 = poly1->next; } // If the power of the 2nd polynomial is greater than that of 1st, // then store 2nd as it is and move its pointer else if (poly1->power < poly2->power) { poly->power = poly2->power; poly->coefficient = poly2->coefficient; poly2 = poly2->next; } // If power of both polynomial expressions is same then // add their coefficients else { poly->power = poly1->power; poly->coefficient = poly1->coefficient + poly2->coefficient; poly1 = poly1->next; poly2 = poly2->next; } poly->next = new Node; poly = poly->next; poly->next = NULL; } while (poly1->next || poly2->next) { if (poly1->next) { poly->power = poly1->power; poly->coefficient = poly1->coefficient; poly1 = poly1->next; } if (poly2->next) { poly->power = poly2->power; poly->coefficient = poly2->coefficient; poly2 = poly2->next; } poly->next = new Node; poly = poly->next; poly->next = NULL; }}Time Complexity: O(m + n), where m and n are the respective numbers of nodes in the first and second lists. |
|