[LeetCode] Add Two Polynomials Represented as Linked Lists

1634. Add Two Polynomials Represented as Linked Lists

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]].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
* Definition for polynomial singly-linked list.
* struct PolyNode {
* int coefficient, power;
* PolyNode *next;
* PolyNode(): coefficient(0), power(0), next(nullptr) {};
* PolyNode(int x, int y): coefficient(x), power(y), next(nullptr) {};
* PolyNode(int x, int y, PolyNode* next): coefficient(x), power(y), next(next) {};
* };
*/

class Solution {
public:
PolyNode* addPoly(PolyNode* poly1, PolyNode* poly2) {
PolyNode* dummy = new PolyNode(-1,-1);
PolyNode* tail = dummy;
while(poly1 and poly2) {
if(poly1->power == poly2->power) {
poly1->coefficient += poly2->coefficient;
if(poly1->coefficient != 0) {
tail->next = poly1;
tail = tail->next;
}
poly1 = poly1->next;
poly2 = poly2->next;
} else if(poly1->power > poly2->power) {
tail->next = poly1;
poly1 = poly1->next;
tail = tail->next;
} else {
tail->next = poly2;
poly2 = poly2->next;
tail = tail->next;
}
tail->next = nullptr;
}
if(poly1) tail->next = poly1;
else if(poly2) tail->next = poly2;

return dummy->next;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/03/01/PS/LeetCode/add-two-polynomials-represented-as-linked-lists/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.