LeetCode 1634. 求两个多项式链表的和

Michael阿明

发布于 2021-09-06 11:36:46

3900

发布于 2021-09-06 11:36:46

文章被收录于专栏：Michael阿明学习之路

文章目录

- 1. 题目
- 2. 解题

1. 题目

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

每个节点有三个属性：

coefficient：该项的系数。项 9x4 的系数是 9 。
power：该项的指数。项 9x4 的指数是 4 。
next：指向下一个节点的指针（引用），如果当前节点为链表的最后一个节点则为 null 。

例如，多项式 5x3 + 4x - 7 可以表示成如下图所示的多项式链表：

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

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

PolyNode 格式：

输入/输出格式表示为 n 个节点的列表，其中每个节点表示为 [coefficient, power] 。例如，多项式 5x3 + 4x - 7 表示为： [[5,3],[4,1],[-7,0]] 。

示例 1：

输入：poly1 = [[1,1]], poly2 = [[1,0]]
输出：[[1,1],[1,0]]
解释：poly1 = x. poly2 = 1. 和为 x + 1.

示例 2：
输入：poly1 = [[2,2],[4,1],[3,0]], poly2 = [[3,2],[-4,1],[-1,0]]
输出：[[5,2],[2,0]]
解释：poly1 = 2x^2 + 4x + 3. poly2 = 3x^2 - 4x - 1. 和为 5x^2 + 2. 注意，我们省略 "0x" 项。

示例 3：
输入：poly1 = [[1,2]], poly2 = [[-1,2]]
输出：[]
解释：和为 0。我们返回空链表。
 

提示：
0 <= n <= 10^4
-10^9 <= PolyNode.coefficient <= 10^9
PolyNode.coefficient != 0
0 <= PolyNode.power <= 10^9
PolyNode.power > PolyNode.next.power

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/add-two-polynomials-represented-as-linked-lists 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

/**
 * 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* temp = new PolyNode(), *cur=temp;
        while(poly1 && poly2)
        {
            if(poly1->power > poly2->power)
            {
                cur->next = poly1;
                cur = cur->next;
                poly1 = poly1->next;
            }
            else if(poly1->power < poly2->power)
            {    
                cur->next = poly2;
                cur = cur->next;
                poly2 = poly2->next;
            }
            else
            {
                int sum = poly1->coefficient + poly2->coefficient;
                if(sum)
                {
                    poly1->coefficient += poly2->coefficient;
                    cur->next = poly1;
                    cur = cur->next;
                }
                poly1 = poly1->next;
                poly2 = poly2->next;
            }
        }
        if(poly1)
            cur->next = poly1;
        else
            cur->next = poly2;
        return temp->next;
    }
};

88 ms 37.8 MB C++

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/08/15 ，如有侵权请联系 cloudcommunity@tencent.com 删除

https