In this article, we will learn c program to add two polynomials using linked list. The program takes an input of coefficient and power separately of 2 different polynomials and add them up to a new polynomial. The time complexity of it is O(m+n), where m & n are the number of nodes in first and second equations respectively.

Algorithm:
1. Read no. of terms in first Polynomial 'p'
2. Read Coefficient and exponent(power) of the first polynomial
3. Read no. of terms in first Polnomial 'q'
4. Read Coefficient and exponent(power) of the second polynomial
5. Traverse both Polynomial 'p' and 'q' respectively
6. Compare the exponent(power) of both polynomials starting from the first node, if the values of both node’s exponent are the same add the coefficients and then copy the added value with node to the result.

To write a c program to add two polynomials using linked list, There are 3 terms we need to understand. Which are "Coefficients", "Power" & "Address of Next Node".
Before we look into the logic of a program, Lets first understand the algorithm to add two polynomials. For that consider mentioned two equations p(x) and q(x).

Input:
p(x) = 3x^2 + 4x^1 + 2
q(x) = 3x^1 + 5

The above image showcases the way to implement the equation to the linked list representation. Also, observe coefficient and power value. Next, we will check for the coefficients of the exponents that have the same value of exponents and add them, which returns the final polynomial.

Output:
Result = 3x^2 + 7x + 7

Program Source Code:
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int coef;
int pow;
struct node *next;
}poly;
{
int ch;
system("clear");
printf("\n\t1)Create 1'st Polynomial ");
printf("\n\t2)Create 2'nd Polynomial ");
printf("\n\t3)Display");
scanf("%d",&ch);
return ch;
}
{
poly *t1,*temp;
int i,flag=1,scan;
t1=(poly *)malloc(sizeof(poly));
temp=(poly *)malloc(sizeof(poly));
for(scan=1;flag==1;scan++)
{
flag=0;
{
if(temp->pow<temp->next->pow)
{
t1->coef=temp->coef;
t1->pow=temp->pow;
temp->coef=temp->next->coef;
temp->pow=temp->next->pow;
temp->next->coef=t1->coef;
temp->next->pow=t1->pow;
flag=1;
}
temp=temp->next;
}
}
}
{
int coef,pow;
printf("\n\tEnter number of terms: ");
int i;
poly *newnode;
{
newnode=(poly *)malloc(sizeof(poly));
system("clear");
printf("\n\tEnter %d term: ",i+1);
scanf("%d",&coef);
printf("\n\tEnter power of %d term: ",i+1);
scanf("%d",&pow);
newnode->coef=coef;
newnode->pow=pow;
while(curr->next)
curr=curr->next;
curr->next=newnode;
curr=newnode;
}
curr->next=NULL;
}
{
printf("\n\tEmpty\n");
else
{
while(temp)
{
if(temp->next==NULL)
{
if(temp->pow==0)
{
printf("%d",temp->coef);
return;
}
if(temp->pow==1)
{
printf("%dx",temp->coef);
return;
}
else
{
printf("%dx^%d",temp->coef,temp->pow);
return;
}
}
else
if(temp->pow==1)
printf("%dx+",temp->coef);
else
if(temp->pow==0)
printf("%d+",temp->coef);
else
printf("%dx^%d+",temp->coef,temp->pow);
temp=temp->next;
}
}
}
{
printf("\n\tEmpty\n");
else
{
while(temp)
{
if(temp->next==NULL)
{
if(temp->pow==0)
{
printf("%d",temp->coef);
return;
}
if(temp->pow==1)
{
printf("%dx",temp->coef);
return;
}
else
{
printf("%dx^%d",temp->coef,temp->pow);
return;
}
}
else
if(temp->pow==1)
printf("%dx+",temp->coef);
else
if(temp->pow==0)
printf("%d+",temp->coef);
else
printf("%dx^%d+",temp->coef,temp->pow);
temp=temp->next;
}
}
}
{
poly *curr1,*curr2,*curr3;
poly *newnode;
while(curr1||curr2)
{
newnode=(poly *)malloc(sizeof(poly));
newnode->next=NULL;
if(curr1->pow>curr2->pow)
{
newnode->coef=curr1->coef;
newnode->pow=curr1->pow;
curr1=curr1->next;
}
else
if(curr1->pow<curr2->pow)
{
newnode->coef=curr2->coef;
newnode->pow=curr2->pow;
curr2=curr2->next;
}
else
{
newnode->coef=curr1->coef+curr2->coef;
newnode->pow=curr2->pow;
curr1=curr1->next;
curr2=curr2->next;
}
if(curr1==NULL&&curr2!=NULL)
{
newnode->coef=curr2->coef;
newnode->pow=curr2->pow;
curr2=curr2->next;
}
if(curr2==NULL&&curr1!=NULL)
{
newnode->coef=curr1->coef;
newnode->pow=curr1->pow;
curr1=curr1->next;
}
curr3->next=newnode;
curr3=newnode;
curr3->next=NULL;
}
}
main()
{
int ch;
{
if(ch==1)
else
if(ch==2)
else
if(ch==3)
{
printf("\n\t1'st Polynomial\t\t");
printf("\n");
printf("\n\t2'nd Polynomial\t\t");
getchar();getchar();
}
else
if(ch==4)
{