#1634 - Add Two Polynomials Represented as Linked Lists
Problem Description
A polynomial linked list is a special type of linked list where every node represents a term in a polynomial expression.
Each node has three attributes:
- coefficient: an integer representing the number multiplier of the term. The coefficient of the term 9x4 is 9.
- power: an integer representing the exponent. The power of the term 9x4 is 4.
- next: a pointer to the next node in the list, or null if it is the last node of the list.
For example, the polynomial 5x3 + 4x - 7 is represented by the polynomial linked list illustrated below: The polynomial linked list must be in its standard form: the polynomial must be in strictly descending order by its power value. Also, terms with a coefficient of 0 are omitted.
Given two polynomial linked list heads, poly1 and poly2, add the polynomials together and return the head of the sum of the polynomials.
PolyNode format: The input/output format is as a list of n nodes, where each node is represented as its [coefficient, power]. For example, the polynomial 5x3 + 4x - 7 would be represented as: [[5,3],[4,1],[-7,0]].
Solution
/**
* Definition for polynomial singly-linked list.
* function PolyNode(x=0, y=0, next=null) {
* this.coefficient = x;
* this.power = y;
* this.next = next;
* }
*/
/**
* @param {PolyNode} poly1
* @param {PolyNode} poly2
* @return {PolyNode}
*/
var addPoly = function(poly1, poly2) {
const dummyHead = new PolyNode();
let current = dummyHead;
let pointer1 = poly1;
let pointer2 = poly2;
while (pointer1 || pointer2) {
let coefficient = 0;
let power = 0;
if (!pointer1) {
coefficient = pointer2.coefficient;
power = pointer2.power;
pointer2 = pointer2.next;
} else if (!pointer2) {
coefficient = pointer1.coefficient;
power = pointer1.power;
pointer1 = pointer1.next;
} else if (pointer1.power > pointer2.power) {
coefficient = pointer1.coefficient;
power = pointer1.power;
pointer1 = pointer1.next;
} else if (pointer2.power > pointer1.power) {
coefficient = pointer2.coefficient;
power = pointer2.power;
pointer2 = pointer2.next;
} else {
coefficient = pointer1.coefficient + pointer2.coefficient;
power = pointer1.power;
pointer1 = pointer1.next;
pointer2 = pointer2.next;
}
if (coefficient !== 0) {
current.next = new PolyNode(coefficient, power);
current = current.next;
}
}
return dummyHead.next;
};