Last Updated: Mar 27, 2024

## 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
}
cout << endl;
}

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

}

// Function to add both list.

// 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);

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

// our algorithm

return 0;
}``````

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)).

## Recursive Approach

The Same problem can be solved using the recursive approach. Although the time complexity of both approaches is the same, still it is good to know different approaches to solve the same problem.

### Algorithm

1. Compare the both the numbers if they are null then simply return

2. Else if the power of both the numbers are same then print the addition of their coefficients and recursively call the function with next number

3. Else if the power of first number is greater than the second number then print the first number and recursively call the function with next number of first polynomial and same value of the second number.

4. Else print the second number and recursively call the function with next polynomial of second number and current value of first number.

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

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

}

// Recursively add two polynomial numbers
// return if both the numbers are null
if (first == nullptr && second == nullptr) return;

// if power of both number are same the
// add their coefficient, print it and recursively call the
// addRecursively function with next number
else if (first->y == second->y){
cout << first->x + second->x << "x^" << first->y << ' ';
}

// if power of first number is greater than the power of second
// then print the first number and recursively call the function
// with next value of that polynomial list
else if(first->y > second->y){
cout << first->x << "x^" << first->y << ' ';
}

// else print the second number and recursively call the function
// with next value of the second polynomial list
else {
cout << second->x << "x^" << second->y << ' ';
}
}

int main(){

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

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

// our algorithm

return 0;
}``````

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 going through each element of both input parameters once effectively.

#### Space Complexity

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

### What is polynomial addition in data structure?

When two polynomials are added, the like terms in the two polynomials are combined. We use the term "like terms" to refer to terms that have the same variable and exponent.

### What is linked list explain?

A linked list is a data structure that arranges elements in a linear order. In contrast to an array, where the linear order is defined by the array indices, a linked list's linear order is determined by a pointer in each object.

### What are Linear data structures?

The elements of linear data structures are organised one after the other in a sequential order. They are simple to construct since the elements are placed in a specific order.

You can also read about the - hash function in data structure

## Conclusion

In this article, we have discussed a question related to LinkedList where we need to add two polynomials represented by a LinkedList. We Discussed two different method to solve the problem. We hope that this blog has enhanced your knowledge and cleared all of your doubts regarding the above question. Check out our articles on our Website to learn more

Visit our Guided Path on Coding Ninjas Studio to upskill yourself in Competitive ProgrammingData Structures and AlgorithmsSystem DesignJavaScript, and many more! Check out the mock test series and participate in the contests hosted on Coding Ninjas Studio to test your proficiency in coding. But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, etc; you must look at the interview experiences, problems, and interview bundle for placement preparations.

Nevertheless, you can also consider our paid courses to give your career an edge over others!

Do upvote the blogs if you find it helpful and engaging!

Happy Learning!

Topics covered
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Pseudocode
2.2.
Implementation in C++
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Recursive Approach
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.