Home
c program
java

Addition of Polynomials Using Linked List | Easiest Explanation

Statement


Given two linked lists representing two different polynomials. We need to find the addition of these two polynomials and represent the resulting polynomial using Linked List.


Example

Input:
     1st number = 5x3 + 4x2 + 2x0
     2nd number = 5x^1 - 5x^0
Output:
        5x3 + 4x2 + 5x1 - 3x0

Understanding the problem


While adding two polynomials we add coefficients of terms with the same powers and the result of this addition is a term with equivalent power.

For example, If we have two polynomials:
  • p(x) = 5x3 + 4x2 + 2
  • g(x) = 5x - 5
and we need to obtain their addition, i.e. p(x) + g(x) then we'll go through following steps:
  1. The first term of p(x) is 5x3 but there is not any term of x3 in the g(x) so we will simply put  5x3 in the result as it is. Result =  5x3
  2. Then we have 4x2, again there is no term of x in g(x) so we will put 4x2 in our result as it is. Result =  5x3 + 4x2
  3.  Then we have 2 and there is also a like term in g(x), i.e. -5 Thus we will add 2 and -5 and will put it into result. Result =  5x3 + 4x2 - 3
  4. Also one term from g(x), 5x , is left so we will add it as it is into the result as there are no other terms in p(x) to check with. Result =  5x3 + 4x2 +5x -3


Based on above steps and rules we will design the code for our real problem, i.e. addition of two polynomials using linked list.

Idea about node of Linked List


The node of the linked list in which we are going to store our polynomial would look something like the one in below picture: 



The node of this linked list consist of three members: 
  • Coefficient: The numeric value which comes before a term.
  • Power: The numeric value to which the exponent of the x has been raised in any term.
  • Add. of the next node: Contains address of the next node.

Understanding the approach using example


Let's take two polynomials as example and perform addition on them.
Assume first polynomial is 6x^3 + 7x^2 + 5x + 4 and another polynomial is 4x^3+3x+7.

As discussed earlier, these two polynomials can be represented in the form of linked list as: 



Now follow the below steps:

1) First of all we will create another linked list with any random coefficient and power let's say -1 and -1, and name it as result. We will use this list to store the resultant polynomial generated after addition.





2.) Create three pointers namely, ptr1, ptr2, ptr3 and make ptr1 to point towards head of linked list 1, ptr2 to point towards head of linked list2 and ptr3 to point towards head of linked list3.





Don't worry about the coding part, currently just focus on the working of this approach.


3). Now stick to this rule, until and unless any one of the pointers out of ptr1 and ptr2 become NULL keep on comparing the powers of the node to which they are pointing. Now while comparing the powers we may have any of below cases: 
  • The power of the node pointed by ptr1 is equal to the power of node pointed by ptr2. In this case add the coefficient part of both the nodes and insert the addition to the next of ptr3 along with the power. And make the ptr1,ptr2 and ptr3 to point towards next node
  • The power of the node pointed by ptr1 is greater than the power of the node pointed by the ptr2. In this case insert that node pointed by ptr1 to the next of the node pointed by ptr3 and make the ptr1 and ptr3 to point towards next node.
  • The power of the node pointed by ptr2 is greater than the power of the node pointed by the ptr1. In this case insert the node pointed by ptr2 to the next of the node pointed by ptr3 and make the ptr2 and ptr3 to point towards next node.
Let's apply the above algo to our example:

Since, the powers of the nodes pointed by ptr1 and ptr2 are equal we will add their respective coefficients and will put the resultant sum along with power to the next of the node pointed by ptr3.

And make the ptr1, ptr2 and ptr3 to point to next node.




The resultant sum of coefficients is 10 and power of node is 3. 10 is added to the coefficient part and 3 is added to the power part of the node next to the node pointed by ptr3.


4). Now the power of node pointed by ptr1 is 2 and power of the node pointed by ptr2 is 1. The node with greater power will be added next to the node pointed by ptr3. So we will add the node pointed by ptr1 to the next of the node pointed by ptr3 and make ptr1 and ptr3 to point to next node.


5). Similarly in the next steps:






We will keep repeating these steps until any of the pointers out of ptr1 or ptr2 reaches null. And after that if any remaining node is present we will simply add it to the next of node pointed by ptr3.

Please note that our resultant list is starting from result->next not from head of result.



Labels : #c program ,#java ,#linked list ,

Post a Comment