Formatted question description: https://leetcode.ca/all/1634.html

# 1634. Add Two Polynomials Represented as Linked Lists

## Level

Medium

## 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`9x^4`

is`9`

.`power`

: an integer representing the exponent. The power of the term`9x^4`

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 `5x^3 + 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 `5x^3 + 4x - 7`

would be represented as: `[[5,3],[4,1],[-7,0]]`

.

**Example 1:**

**Input:** poly1 = [[1,1]], poly2 = [[1,0]]

**Output:** [[1,1],[1,0]]

**Explanation:** poly1 = x. poly2 = 1. The sum is x + 1.

**Example 2:**

**Input:** poly1 = [[2,2],[4,1],[3,0]], poly2 = [[3,2],[-4,1],[-1,0]]

**Output:** [[5,2],[2,0]]

**Explanation:** poly1 = 2x2 + 4x + 3. poly2 = 3x2 - 4x - 1. The sum is 5x2 + 2. Notice that we omit the “0x” term.

**Example 3:**

**Input:** poly1 = [[1,2]], poly2 = [[-1,2]]

**Output:** []

**Explanation:** The sum is 0. We return an empty list.

**Constraints:**

`0 <= n <= 10^4`

`-10^9 <= PolyNode.coefficient <= 10^9`

`PolyNode.coefficient != 0`

`0 <= PolyNode.power <= 10^9`

`PolyNode.power > PolyNode.next.power`

## Solution

Create a `dummyHead`

for the result polynomial. Each time compare the current nodes of `poly1`

and `poly2`

, which are `node1`

and `node2`

.

If they have the same power, calculate the sum of the coefficients of `node1`

and `node2`

. If the sum is not 0, append it to the result polynomial, move the node of the result polynomial one step ahead. Otherwise, do not append it to the result polynomial. Move `node1`

and `node2`

one step ahead.

If they have different powers, append the node with the greater power to the result polynomial, move the node of the result polynomial one step ahead, and move the corresponding node (with the greater power) one step ahead.

When one of the nodes in `node1`

and `node2`

becomes empty, append the remaining nodes of the other polynomial to the result node.

Finally, return `dummyHead.next`

.

```
/**
* Definition for polynomial singly-linked list.
* class PolyNode {
* int coefficient, power;
* PolyNode next = null;
* PolyNode() {}
* PolyNode(int x, int y) { this.coefficient = x; this.power = y; }
* PolyNode(int x, int y, PolyNode next) { this.coefficient = x; this.power = y; this.next = next; }
* }
*/
class Solution {
public PolyNode addPoly(PolyNode poly1, PolyNode poly2) {
PolyNode dummyHead = new PolyNode();
PolyNode node = dummyHead;
PolyNode node1 = poly1, node2 = poly2;
while (node1 != null && node2 != null) {
if (node1.power == node2.power) {
int nextCoefficient = node1.coefficient + node2.coefficient;
int nextPower = node1.power;
if (nextCoefficient != 0) {
PolyNode nextNode = new PolyNode(nextCoefficient, nextPower);
node.next = nextNode;
node = node.next;
}
node1 = node1.next;
node2 = node2.next;
} else if (node1.power > node2.power) {
PolyNode nextNode = new PolyNode(node1.coefficient, node1.power);
node.next = nextNode;
node = node.next;
node1 = node1.next;
} else {
PolyNode nextNode = new PolyNode(node2.coefficient, node2.power);
node.next = nextNode;
node = node.next;
node2 = node2.next;
}
}
if (node1 != null)
node.next = node1;
else if (node2 != null)
node.next = node2;
return dummyHead.next;
}
}
```