Problem#
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 **9**x4
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:
graph LR;
A("coefficient: 5 power:3") --> B("coefficient: 4 power:1") --> C("coefficient: -7 power:0") --> D("null")
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]]
.
Examples#
Example 1#
graph TB;
subgraph poly1
A("coefficient: 1 power:1"):::right --> B("null"):::right
end
subgraph poly2
C(" "):::hidden ~~~ D("coefficient: 1 power:0") --> E("null"):::right
end
poly1 ~~~ poly2
classDef hidden display:none;
classDef right align:center;
graph LR;
A("coefficient: 1 power:1"):::right ---> B("null"):::right
C(" "):::hidden ~~~ D("coefficient: 1 power:0") --> E("null"):::right
classDef hidden display:none;
classDef right align:center;
1
2
3
Input: poly1 = [[ 1 , 1 ]], poly2 = [[ 1 , 0 ]]
Output: [[ 1 , 1 ],[ 1 , 0 ]]
Explanation: poly1 = x. poly2 = 1. The sum is x + 1.
Example 2#
1
2
3
Input: poly1 = [[ 2 , 2 ],[ 4 , 1 ],[ 3 , 0 ]], poly2 = [[ 3 , 2 ],[- 4 , 1 ],[- 1 , 0 ]]
Output: [[ 5 , 2 ],[ 2 , 0 ]]
Explanation: poly1 = 2 x2 + 4 x + 3. poly2 = 3 x2 - 4 x - 1. The sum is 5 x2 + 2. Notice that we omit the "0x" term.
Example 3#
1
2
3
Input: poly1 = [[ 1 , 2 ]], poly2 = [[- 1 , 2 ]]
Output: []
Explanation: The sum is 0. We return an empty list.
Solution#
Method 1 – Two Pointers Merge#
Intuition#
The key idea is to traverse both polynomial linked lists simultaneously, comparing the powers of the current nodes. Since both lists are sorted in descending order of power, we can merge them similarly to merging two sorted lists. When powers match, sum the coefficients; if the sum is non-zero, add to the result. If powers differ, add the term with the higher power to the result.
Approach#
Initialize a dummy node to build the result list and a pointer cur
to track the current node.
Use two pointers, p1
and p2
, to traverse poly1
and poly2
.
While both pointers are not null:
If p1.power > p2.power
, append p1
’s term to the result and move p1
forward.
If p1.power < p2.power
, append p2
’s term to the result and move p2
forward.
If p1.power == p2.power
, sum the coefficients. If the sum is not zero, create a new node with the sum and the same power, and append to the result. Move both pointers forward.
Append any remaining nodes from either list.
Return the next node of the dummy as the head of the result.
Code#
Cpp
Go
Java
Kotlin
Python
Rust
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
class Solution {
public :
PolyNode* addPoly(PolyNode* poly1, PolyNode* poly2) {
PolyNode dummy (0 , 0 );
PolyNode* ans = & dummy;
while (poly1 && poly2) {
if (poly1-> power > poly2-> power) {
ans-> next = poly1;
poly1 = poly1-> next;
} else if (poly1-> power < poly2-> power) {
ans-> next = poly2;
poly2 = poly2-> next;
} else {
int sum = poly1-> coefficient + poly2-> coefficient;
if (sum != 0 ) {
ans-> next = new PolyNode(sum, poly1-> power);
ans = ans-> next;
}
poly1 = poly1-> next;
poly2 = poly2-> next;
continue ;
}
ans = ans-> next;
}
ans-> next = poly1 ? poly1 : poly2;
return dummy.next;
}
};
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
func addPoly (poly1 * PolyNode , poly2 * PolyNode ) * PolyNode {
dummy := & PolyNode {}
ans := dummy
for poly1 != nil && poly2 != nil {
if poly1 .Power > poly2 .Power {
ans .Next = poly1
poly1 = poly1 .Next
ans = ans .Next
} else if poly1 .Power < poly2 .Power {
ans .Next = poly2
poly2 = poly2 .Next
ans = ans .Next
} else {
sum := poly1 .Coefficient + poly2 .Coefficient
if sum != 0 {
ans .Next = & PolyNode {Coefficient : sum , Power : poly1 .Power }
ans = ans .Next
}
poly1 = poly1 .Next
poly2 = poly2 .Next
}
}
if poly1 != nil {
ans .Next = poly1
} else {
ans .Next = poly2
}
return dummy .Next
}
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
class Solution {
public PolyNode addPoly (PolyNode poly1, PolyNode poly2) {
PolyNode dummy = new PolyNode(0, 0);
PolyNode ans = dummy;
while (poly1 != null && poly2 != null ) {
if (poly1.power > poly2.power ) {
ans.next = poly1;
poly1 = poly1.next ;
ans = ans.next ;
} else if (poly1.power < poly2.power ) {
ans.next = poly2;
poly2 = poly2.next ;
ans = ans.next ;
} else {
int sum = poly1.coefficient + poly2.coefficient ;
if (sum != 0) {
ans.next = new PolyNode(sum, poly1.power );
ans = ans.next ;
}
poly1 = poly1.next ;
poly2 = poly2.next ;
}
}
ans.next = (poly1 != null ) ? poly1 : poly2;
return dummy.next ;
}
}
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
class Solution {
fun addPoly (poly1: PolyNode?, poly2: PolyNode?): PolyNode? {
val dummy = PolyNode(0 , 0 )
var ans = dummy
var p1 = poly1
var p2 = poly2
while (p1 != null && p2 != null ) {
when {
p1.power > p2.power -> {
ans.next = p1
p1 = p1.next
ans = ans.next!!
}
p1.power < p2.power -> {
ans.next = p2
p2 = p2.next
ans = ans.next!!
}
else -> {
val sum = p1.coefficient + p2.coefficient
if (sum != 0 ) {
ans.next = PolyNode(sum, p1.power)
ans = ans.next!!
}
p1 = p1.next
p2 = p2.next
}
}
}
ans.next = p1 ?: p2
return dummy.next
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution :
def addPoly (self, poly1: 'PolyNode | None' , poly2: 'PolyNode | None' ) -> 'PolyNode | None' :
dummy = PolyNode(0 , 0 )
ans = dummy
while poly1 and poly2:
if poly1. power > poly2. power:
ans. next = poly1
poly1 = poly1. next
ans = ans. next
elif poly1. power < poly2. power:
ans. next = poly2
poly2 = poly2. next
ans = ans. next
else :
s = poly1. coefficient + poly2. coefficient
if s != 0 :
ans. next = PolyNode(s, poly1. power)
ans = ans. next
poly1 = poly1. next
poly2 = poly2. next
ans. next = poly1 if poly1 else poly2
return dummy. next
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
impl Solution {
pub fn add_poly (mut poly1: Option< Box< PolyNode>> , mut poly2: Option< Box< PolyNode>> ) -> Option< Box< PolyNode>> {
let mut dummy = Box::new(PolyNode::new(0 , 0 ));
let mut ans = & mut dummy;
while poly1.is_some() && poly2.is_some() {
let (c1, p1) = {
let node = poly1.as_ref().unwrap();
(node.coefficient, node.power)
};
let (c2, p2) = {
let node = poly2.as_ref().unwrap();
(node.coefficient, node.power)
};
if p1 > p2 {
let next = poly1.as_mut().unwrap().next.take();
ans.next = poly1;
ans = ans.next.as_mut().unwrap();
poly1 = next;
} else if p1 < p2 {
let next = poly2.as_mut().unwrap().next.take();
ans.next = poly2;
ans = ans.next.as_mut().unwrap();
poly2 = next;
} else {
let sum = c1 + c2;
if sum != 0 {
ans.next = Some(Box::new(PolyNode::new(sum, p1)));
ans = ans.next.as_mut().unwrap();
}
poly1 = poly1.unwrap().next;
poly2 = poly2.unwrap().next;
}
}
ans.next = if poly1.is_some() { poly1 } else { poly2 };
dummy.next
}
}
Complexity#
⏰ Time complexity: O(n + m)
, where n
and m
are the lengths of the two lists.
🧺 Space complexity: O(n + m)
for the result list.