1634. Add Two Polynomials Represented as Linked Lists #

题目 #

多项式链表是一种特殊形式的链表，每个结点表示多项式的一项。

每个结点有三个属性：

coefficient：该项的系数
power：该项的指数
next：指向下一个结点的指针，如果当前结点为链表的最后一个结点则为 null

多项式链表是标准形式的，即多项式严格按指数 power 的递减顺序排列。系数 coefficient 为 0 的项需要省略。

给定两个多项式链表的头结点 poly1 和 poly2，返回它们的和的头结点。

思路 #

代码 #

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 mergePoly(PolyNode poly1, PolyNode poly2) {
        if (poly1 == null && poly2 == null) return null;
        
        if (poly1 == null) return poly2;
        
        if (poly2 == null) return poly1;
        
        if (poly1.power == poly2.power) {
            poly1.coefficient += poly2.coefficient;
            if (poly1.coefficient == 0) return mergePoly(poly1.next, poly2.next);
            poly1.next = mergePoly(poly1.next, poly2.next);
            return poly1;
        } else if (poly1.power > poly2.power) {
            poly1.next = mergePoly(poly1.next, poly2);
            return poly1;
        } else {
            poly2.next = mergePoly(poly1, poly2.next);
            return poly2;
        }
    }
}