1// Aim: Program to perform Polynomial Multiplication using Linked List.
2#include <stdio.h>
3#include <stdlib.h>
4struct node{
5    int coeff,expo;
6    struct node *link;
7}*start1,*start2,*temp1,*temp2,*start3,*temp3,*head,*newNode,*t1,*t2,*X;
8void create1();
9void create2();
10void multiply();
11void create1(){
12    char ch;
13    start1=NULL;
14    int co,ex;
15    do{
16        head=(struct node *)malloc(sizeof(struct node));
17        printf("Enter coeff and expo of the term: ");
18        scanf("%d %d",&co,&ex);
19        head->coeff=co;
20        head->expo=ex;
21        head->link=NULL;
22        if (start1==NULL){
23            start1=head;
24            temp1=head;
25        }
26        else{
27            temp1->link=head;
28            temp1=head;
29        }
30        printf("Want to add more?(y/n): ");
31        scanf("%c",&ch);
32        scanf("%c",&ch);
33    }while (ch=='y');
34}
35void create2(){
36    char ch;
37    start2=NULL;
38    int co,ex;
39    do{
40        head=(struct node *)malloc(sizeof(struct node));
41        printf("Enter coeff and expo of the term: ");
42        scanf("%d %d",&co,&ex);
43        head->coeff=co;
44        head->expo=ex;
45        head->link=NULL;
46        if (start2==NULL){
47            start2=head;
48            temp2=head;
49        }
50        else{
51            temp2->link=head;
52            temp2=head;
53        }
54        printf("Want to add more?(y/n): ");
55        scanf("%c",&ch);
56        scanf("%c",&ch);
57    }while (ch=='y');
58}
59void multiply(){
60    temp1=start1;
61    temp2=start2;
62    start3=NULL;
63    int x,y;
64    while (temp1!=NULL){
65        while (temp2!=NULL){
66            x=temp1->coeff*temp2->coeff;
67            y=temp1->expo+temp2->expo;
68            newNode=(struct node*)malloc(sizeof(struct node));
69            newNode->coeff=x;
70            newNode->expo=y;
71            newNode->link=NULL;
72            if (start3==NULL){
73                start3=newNode;
74                temp3=newNode;
75            }
76            else{
77                temp3->link=newNode;
78                temp3=newNode;
79            }
80            temp2=temp2->link;
81        }
82        temp1=temp1->link;
83        temp2=start2;
84    }
85    temp3=start3;
86    while (temp3!=NULL){
87        t1=temp3;
88        t2=temp3->link;
89        while (t2!=NULL){
90            if (temp3->expo==t2->expo){
91                temp3->coeff=temp3->coeff+t2->coeff;
92                t1->link=t2->link;
93                X=t2;
94                t2=t2->link;
95                free(X);
96            }
97            else{
98                t1=t2;
99                t2=t2->link;
100            }
101        }
102        temp3=temp3->link;
103    }
104    printf("First Polynomial\n");
105    temp1=start1;
106    while (temp1->link!=NULL){
107        printf("%dx^%d+",temp1->coeff,temp1->expo);
108        temp1=temp1->link;
109    }
110    printf("%dx^%d\n",temp1->coeff,temp1->expo);
111    printf("Second Polynomial\n");
112    temp2=start2;
113    while (temp2->link!=NULL){
114        printf("%dx^%d+",temp2->coeff,temp2->expo);
115        temp2=temp2->link;
116    }
117    printf("%dx^%d\n",temp2->coeff,temp2->expo);
118    printf("Product polynomial\n");
119    temp3=start3;
120    while (temp3->link!=NULL){
121        printf("%dx%d+",temp3->coeff,temp3->expo);
122        temp3=temp3->link;
123    }
124    printf("%dx%d",temp3->coeff,temp3->expo);
125} 
126void main(){
127    printf("Enter first polynomial \n");
128    create1();
129    printf("Enter second polynomial \n");
130    create2();
131    multiply();
132}