1+ // Multiplication of Two polynomial using Linked List
2+
3+ mport java .util .*;
4+ class POLY_MUL
5+ {
6+
7+ // Node structure containing powerer
8+ // and coefficient of variable
9+ static class Node {
10+ int coeff , power ;
11+ Node next ;
12+ };
13+
14+ // Function add a new node at the end of list
15+ static Node addnode (Node start , int coeff , int power )
16+ {
17+ // Create a new node
18+ Node newnode = new Node ();
19+ newnode .coeff = coeff ;
20+ newnode .power = power ;
21+ newnode .next = null ;
22+
23+ // If linked list is empty
24+ if (start == null )
25+ return newnode ;
26+
27+ // If linked list has nodes
28+ Node ptr = start ;
29+ while (ptr .next != null )
30+ ptr = ptr .next ;
31+ ptr .next = newnode ;
32+
33+ return start ;
34+ }
35+
36+ // Functionn To Display The Linked list
37+ static void printList ( Node ptr )
38+ {
39+ while (ptr .next != null ) {
40+ System .out .print ( ptr .coeff + "x^" + ptr .power + " + " );
41+
42+ ptr = ptr .next ;
43+ }
44+ System .out .print ( ptr .coeff +"\n " );
45+ }
46+
47+ // Function to add coefficients of
48+ // two elements having same powerer
49+ static void removeDuplicates (Node start )
50+ {
51+ Node ptr1 , ptr2 , dup ;
52+ ptr1 = start ;
53+
54+ /* Pick elements one by one */
55+ while (ptr1 != null && ptr1 .next != null ) {
56+ ptr2 = ptr1 ;
57+
58+ // Compare the picked element
59+ // with rest of the elements
60+ while (ptr2 .next != null ) {
61+
62+ // If powerer of two elements are same
63+ if (ptr1 .power == ptr2 .next .power ) {
64+
65+ // Add their coefficients and put it in 1st element
66+ ptr1 .coeff = ptr1 .coeff + ptr2 .next .coeff ;
67+ dup = ptr2 .next ;
68+ ptr2 .next = ptr2 .next .next ;
69+
70+ }
71+ else
72+ ptr2 = ptr2 .next ;
73+ }
74+ ptr1 = ptr1 .next ;
75+ }
76+ }
77+
78+ // Function two Multiply two polynomial Numbers
79+ static Node multiply (Node poly1 , Node poly2 ,
80+ Node poly3 )
81+ {
82+
83+ // Create two pointer and store the
84+ // address of 1st and 2nd polynomials
85+ Node ptr1 , ptr2 ;
86+ ptr1 = poly1 ;
87+ ptr2 = poly2 ;
88+ while (ptr1 != null ) {
89+ while (ptr2 != null ) {
90+ int coeff , power ;
91+
92+ // Multiply the coefficient of both
93+ // polynomials and store it in coeff
94+ coeff = ptr1 .coeff * ptr2 .coeff ;
95+
96+ // Add the powerer of both polynomials
97+ // and store it in power
98+ power = ptr1 .power + ptr2 .power ;
99+
100+ // Invoke addnode function to create
101+ // a newnode by passing three parameters
102+ poly3 = addnode (poly3 , coeff , power );
103+
104+ // move the pointer of 2nd polynomial
105+ // two get its next term
106+ ptr2 = ptr2 .next ;
107+ }
108+
109+ // Move the 2nd pointer to the
110+ // starting point of 2nd polynomial
111+ ptr2 = poly2 ;
112+
113+ // move the pointer of 1st polynomial
114+ ptr1 = ptr1 .next ;
115+ }
116+
117+ // this function will be invoke to add
118+ // the coefficient of the elements
119+ // having same powerer from the resultant linked list
120+ removeDuplicates (poly3 );
121+ return poly3 ;
122+ }
123+
124+ // Driver Code
125+ public static void main (String args [])
126+ {
127+
128+ Node poly1 = null , poly2 = null , poly3 = null ;
129+
130+ // Creation of 1st Polynomial: 3x^2 + 5x^1 + 6
131+ poly1 = addnode (poly1 , 3 , 2 );
132+ poly1 = addnode (poly1 , 5 , 1 );
133+ poly1 = addnode (poly1 , 6 , 0 );
134+
135+ // Creation of 2nd polynomial: 6x^1 + 8
136+ poly2 = addnode (poly2 , 6 , 1 );
137+ poly2 = addnode (poly2 , 8 , 0 );
138+
139+ // Displaying 1st polynomial
140+ System .out .print ("--------------1st Polynomial:------------------------ " );
141+ printList (poly1 );
142+
143+ // Displaying 2nd polynomial
144+ System .out .print ("--------------2nd Polynomial:------------------------ " );
145+ printList (poly2 );
146+
147+ // calling multiply function
148+ poly3 = multiply (poly1 , poly2 , poly3 );
149+
150+ // Displaying Resultant Polynomial
151+ System .out .print ( "-------------------Resultant Polynomial:- -------------" );
152+ printList (poly3 );
153+
154+ }
155+
156+
157+ }
0 commit comments