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

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 <= 104
-109 <= PolyNode.coefficient <= 109
PolyNode.coefficient != 0
0 <= PolyNode.power <= 109
PolyNode.power > PolyNode.next.power

两个多项式相加。

题意是给两个以链表表示的多项式，请以链表形式输出他们相加的结果。这道题不难类似21题 merge two linked lists，注意实现细节就行。既然是链表题，我们还是需要一个dummy node放在最前面。对于这两个链表，我们首先需要判断的是他们两人谁的power大，谁大就需要把谁放在前面。例子中没有给出，但是test case里面是存在类似这样的case的。

3x^3 + 2x^2, 3x^2 + 2x^2

power相同的情况下，则把两个node的power相加；但是如果两个node的power相加等于0的话，则说明这一项两边抵消了，则两个链表可以分别移动到下一个节点了。

时间O(n)

空间O(1)

Java实现

 1 /**
 2  * Definition for polynomial singly-linked list.
 3  * class PolyNode {
 4  *     int coefficient, power;
 5  *     PolyNode next = null;
 6  
 7  *     PolyNode() {}
 8  *     PolyNode(int x, int y) { this.coefficient = x; this.power = y; }
 9  *     PolyNode(int x, int y, PolyNode next) { this.coefficient = x; this.power = y; this.next = next; }
10  * }
11  */
12 
13 class Solution {
14     public PolyNode addPoly(PolyNode poly1, PolyNode poly2) {
15         PolyNode ans = new PolyNode(0, 0);
16         PolyNode cur = ans;
17         while (poly1 != null || poly2 != null) {
18             if (poly1 == null) {
19                 cur.next = new PolyNode(poly2.coefficient, poly2.power);
20                 poly2 = poly2.next;
21             } else if (poly2 == null) {
22                 cur.next = new PolyNode(poly1.coefficient, poly1.power);
23                 poly1 = poly1.next;
24             } else {
25                 if (poly1.power > poly2.power) {
26                     cur.next = new PolyNode(poly1.coefficient, poly1.power);
27                     poly1 = poly1.next;
28                 } else if (poly1.power < poly2.power) {
29                     cur.next = new PolyNode(poly2.coefficient, poly2.power);
30                     poly2 = poly2.next;
31                 } else {
32                     int coeffi = poly1.coefficient + poly2.coefficient;
33                     if (coeffi == 0) {
34                         poly1 = poly1.next;
35                         poly2 = poly2.next;
36                         continue;
37                     } else {
38                         cur.next = new PolyNode(coeffi, poly1.power);
39                         poly1 = poly1.next;
40                         poly2 = poly2.next;
41                     }
42                 }
43             }
44             cur = cur.next;
45         }
46         return ans.next;
47     }
48 }