Polynomial Addition Using Linked List Example In Hindi | DSA | Engineering Students | C++ | JAVA |

Add Two Polynomials

To add two polynomials, we can add the coefficients of like terms and generate a new linked list for the resulting polynomial. For example, we can use two liked lists to represent polynomials 2-4x+5x^2 and 1+2x - 3x^3:

two polynomials
When we add them together, we can group the like terms and generate the result 3 - 2x^2 + 5x^2 - 3x^3:

sum result
Since both linked list are ordered by the power, we can use a two-pointer method to merge the two sorted linked list:

In this algorithm, we first create two pointers, p1 and p2, to the head pointers of the two input polynomials. Then, we generate the new polynomial nodes based on the powers of these two pointers. There are three cases:

p1‘s power is greater than p2‘s power: In this case, we append a new node with p1‘s power and coefficient. Also, we move p1 to the next node.
p2‘s power is greater than p1‘s power: In this case, we append a new node with p2‘s power and coefficient. Also, we move p2 to the next node.
p1 and p2 have the same power: In this case, the new coefficient is the total of p1‘s coefficient and p2‘s coefficient. If the new coefficient is not 0, we append a new node with the same power and the new coefficient. Also, we move both p1 and p2 to the next nodes.
After that, we continue to append the remaining nodes from p1 or p2 until we finish the calculation on all nodes.

The append function can create a new linked list node based on the input power and coefficient. Also, it appends the new node to the tail node and returns the new tail node:

This algorithm traverses each linked list node only once. Therefore, the overall running time is O(n + m), where n and m are the number of terms for the two input polynomials.