Adding two polynomials using Linked List

Introduction

The LinkedList data structure is a versatile data structure that can be used in a variety of situations. Many of the queries answered at most firms come from LinkedList. As a result, it is critical to have a full comprehension of this Data Structure.

In this blog, we'll look at a question about LinkedList and two possible ways that can be utilized to tackle the problem.

Recommended Topic, Floyds Algorithm

Problem Statement

A linked list is being used to represent two polynomial expressions. Create a function to combine these lists and print the result on the screen.

Sample Examples

Example 1

Input

Output

Explanation

Adding 5x^2 + 4x^1 with 5x^2 + 2x^1 we get 10x^2 + 6x^1 as the result.

Example 2

Input

Output

Explanation

Adding 2x^2 + 4x^1 with 3x^2 + 2x^1 we get 5x^2 + 6x^1 as the result.

Approach

We compare the power of the first polynomial of both lists. If it is the same then we simply add their coefficient and push them into the resultant list otherwise we push the polynomial of the list whose power is greater than the other polynomial.

Pseudocode

1. Declare variables that point to the head of the linked list.
    
2. Compare the power of the first polynomial of both lists.
   
   1. If it is the same then add their coefficients and push them into the resultant list. Also, increment both the variables so that it points to the next polynomial.
       
   2. Else, Push the polynomial of the list whose power is greater than the other. Also, increment that particular list.
       
3. Keep repeating the 2nd step until one of the variables reaches the end of the list.
    
4. Then check for the remaining data in both of the lists and add it to the resultant list.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// Represents the single polynomial
class Node{
    public:
        int x;
        int y;
        Node *next;
        
        Node(int x, int y, Node *next){
            this->x = x;
            this->y = y;
            this->next = next;
        }
};


// Simply Prints the List to the Screen
void printList(Node *head){
  while(head!=NULL){
    cout<<head->x<<"x"<<"^"<<head->y << " ";
    head = head->next;
  }
  cout << endl;
}


// Creates a new node and inserts it into the end
// of the head node
void insertNode(Node *head, int x, int y){
    Node *newNode = new Node(x, y, nullptr);
    while(head->next != nullptr){
        head = head->next;
    }


    head->next = newNode;
}


// Function to add both list.
void add(Node *first, Node *second){


    // Resultant list
    Node *result = nullptr;

    // Loop to add both the list
    // until one of the list reaches to its end
    while(first && second){


        // saves current result
        int x, y;

        // if power of both the polynomial is same
        // we simply add their coefficient and increment the
        // pointer to next node
        if(first->y == second->y){
            x = first->x+second->x;
            y = first->y;
            first = first->next;
            second = second->next;
        }

        // if power of first polynomial is greater than
        // the second one then save its coefficient and power
        // into the result and increment its pointer
        else if(first->y > second->y){
            x = first->x;
            y = first->y;
            first = first->next;
        }

        // if power of second polynomial is greater than
        // the first one. then save its coefficient and power
        // into the result and increment its pointer
        else{
            x = second->x;
            y = second->y;
            second = second->next;
        }

        // if resultant list is empty we create a new node
        // else we simply add the value at the end of our resultant list
        if(result == nullptr) result = new Node(x, y, nullptr);
        else insertNode(result, x, y);
   }

   // After completion of the above loop there might be a possibility
   // that one of the two polynomial lists have some unchecked data
   // below two loops are just adding the remaining data into our
   // resultant list
   while(first){
        if(result == nullptr) result = new Node(first->x, first->y, nullptr);
        else insertNode(result, first->x, first->y);
        first = first->next;
   }

   while(second){
        if(result == nullptr) result = new Node(second->x, second->y, nullptr);
        else insertNode(result, second->x, second->y);
        second = second->next;
   }


    // printing the resultant list
   printList(result);
}

int main(){

    // First polynomial
    Node *head = new Node(5, 2, nullptr);
    insertNode(head, 4, 1);

    // second polynomial
    Node *head2 = new Node(5, 2, nullptr);
    insertNode(head2, 2, 1);

    // our algorithm
    add(head, head2);

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

5x^2   4x^1
5x^2   2x^1

Output

10x^2   6x^1

Time Complexity

The time required to add both lists is O(n + m), where n and m represent the length of both lists respectively.  As we are iterating through both lists once.

Space Complexity

As we are saving the elements in the resultant list so the space complexity of our algorithm is O(max(n, m)).