A polynomial is an algebraic expression consisting of one or more terms, where each term consists of a variable raised to a non-negative integer power multiplied by a numerical coefficient. Polynomials are widely used in mathematics and science to represent a wide range of functions, from simple curves to complex shapes.
To add two polynomials, we first group the terms with the same exponent and add their coefficients. We then combine the resulting terms in decreasing order of exponent to form the sum polynomial. If one polynomial has terms with exponents that are not present in the other polynomial, we simply include those terms in the sum polynomial. The resulting sum polynomial is also a polynomial, with coefficients and exponents that are the sum of the corresponding coefficients and exponents of the input polynomials.
class Node(var coeff: Int, var exp: Int) {
var next: Node? = null
}
Node class: This class represents a node in the linked list. Each node has two fields: coeff, which represents the coefficient of the term in the polynomial, and exp, which represents the exponent of the term in the polynomial. The next field is a reference to the next node in the linked list.
fun addPolynomials(poly1: Node?, poly2: Node?): Node? {
var res: Node? = null
var tail: Node? = null
var curr1 = poly1
var curr2 = poly2
while (curr1 != null && curr2 != null) {
if (curr1.exp == curr2.exp) {
val sum = curr1.coeff + curr2.coeff
if (sum != 0) {
val newNode = Node(sum, curr1.exp)
if (tail == null) {
res = newNode
tail = newNode
} else {
tail.next = newNode
tail = newNode
}
}
curr1 = curr1.next
curr2 = curr2.next
} else if (curr1.exp > curr2.exp) {
val newNode = Node(curr1.coeff, curr1.exp)
if (tail == null) {
res = newNode
tail = newNode
} else {
tail.next = newNode
tail = newNode
}
curr1 = curr1.next
} else {
val newNode = Node(curr2.coeff, curr2.exp)
if (tail == null) {
res = newNode
tail = newNode
} else {
tail.next = newNode
tail = newNode
}
curr2 = curr2.next
}
}
while (curr1 != null) {
val newNode = Node(curr1.coeff, curr1.exp)
if (tail == null) {
res = newNode
tail = newNode
} else {
tail.next = newNode
tail = newNode
}
curr1 = curr1.next
}
while (curr2 != null) {
val newNode = Node(curr2.coeff, curr2.exp)
if (tail == null) {
res = newNode
tail = newNode
} else {
tail.next = newNode
tail = newNode
}
curr2 = curr2.next
}
return res
}addPolynomials function: This function takes two polynomial linked lists as input and returns a new polynomial linked list representing the sum of the two input polynomials. The function works as follows:
We create a dummy node to act as the head of the result linked list. We initialize temp to point to this node.
We traverse both input linked lists simultaneously, adding the coefficients of terms with the same exponent and creating a new node with the resulting coefficient and exponent. We append this node to the result linked list.
If one input linked list has a term with a larger exponent than the largest exponent in the other linked list, we add that term and its coefficient to the result linked list.
When we finish traversing both linked lists, we return the next node after the dummy node in the result linked list.
class Node(var coeff: Int, var exp: Int) {
var next: Node? = null
}
fun addPolynomials(poly1: Node?, poly2: Node?): Node? {
var res: Node? = null
var tail: Node? = null
var curr1 = poly1
var curr2 = poly2
while (curr1 != null && curr2 != null) {
if (curr1.exp == curr2.exp) {
val sum = curr1.coeff + curr2.coeff
if (sum != 0) {
val newNode = Node(sum, curr1.exp)
if (tail == null) {
res = newNode
tail = newNode
} else {
tail.next = newNode
tail = newNode
}
}
curr1 = curr1.next
curr2 = curr2.next
} else if (curr1.exp > curr2.exp) {
val newNode = Node(curr1.coeff, curr1.exp)
if (tail == null) {
res = newNode
tail = newNode
} else {
tail.next = newNode
tail = newNode
}
curr1 = curr1.next
} else {
val newNode = Node(curr2.coeff, curr2.exp)
if (tail == null) {
res = newNode
tail = newNode
} else {
tail.next = newNode
tail = newNode
}
curr2 = curr2.next
}
}
while (curr1 != null) {
val newNode = Node(curr1.coeff, curr1.exp)
if (tail == null) {
res = newNode
tail = newNode
} else {
tail.next = newNode
tail = newNode
}
curr1 = curr1.next
}
while (curr2 != null) {
val newNode = Node(curr2.coeff, curr2.exp)
if (tail == null) {
res = newNode
tail = newNode
} else {
tail.next = newNode
tail = newNode
}
curr2 = curr2.next
}
return res
}
fun main() {
// create polynomial 1: 2x^3 + 3x^2 + 1x^1 + 5x^0
val poly1 = Node(2, 3)
poly1.next = Node(3, 2)
poly1.next?.next = Node(1, 1)
poly1.next?.next?.next = Node(5, 0)
// create polynomial 2: 3x^3 + 1x^1 + 2x^0
val poly2 = Node(3, 3)
poly2.next = Node(1, 1)
poly2.next?.next = Node(2, 0)
// print polynomial 1
print("${poly1.coeff}x^${poly1.exp} + ")
var temp = poly1.next
while (temp != null) {
print("${temp.coeff}x^${temp.exp} + ")
temp = temp.next
}
println()
// print polynomial 2
temp = poly2
while (temp != null) {
print("${temp.coeff}x^${temp.exp} + ")
temp = temp.next
}
println()
// add polynomials
val res = addPolynomials(poly1, poly2)
// print result
temp = res
while (temp != null) {
print("${temp.coeff}x^${temp.exp} + ")
temp = temp.next
}
println()
}main function, we create two polynomial linked lists poly1 and poly2, print them using a loop, add them using the addPolynomials function, and then print the result. The output of running this code should be:
2x^3 + 3x^2 + 1x^1 + 5x^0 +
3x^3 + 1x^1 + 2x^0 +
5x^3 + 3x^2 + 2x^1 + 7x^0 +