文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

多項(xiàng)式鏈表是一種特殊形式的鏈表，每個節(jié)點(diǎn)表示多項(xiàng)式的一項(xiàng)。

每個節(jié)點(diǎn)有三個屬性：

• coefficient：該項(xiàng)的系數(shù)。項(xiàng) 9x⁴ 的系數(shù)是 9 。
• power：該項(xiàng)的指數(shù)。項(xiàng) 9x⁴ 的指數(shù)是 4 。
• next：指向下一個節(jié)點(diǎn)的指針（引用），如果當(dāng)前節(jié)點(diǎn)為鏈表的最后一個節(jié)點(diǎn)則為 null 。

例如，多項(xiàng)式 5x³ + 4x - 7 可以表示成如下圖所示的多項(xiàng)式鏈表：

多項(xiàng)式鏈表必須是標(biāo)準(zhǔn)形式的，即多項(xiàng)式必須 嚴(yán)格 按指數(shù) power 的遞減順序排列（即降冪排列）。
另外，系數(shù) coefficient 為 0 的項(xiàng)需要省略。

給定兩個多項(xiàng)式鏈表的頭節(jié)點(diǎn) poly1 和 poly2，返回它們的和的頭節(jié)點(diǎn)。

PolyNode 格式：

輸入/輸出格式表示為 n 個節(jié)點(diǎn)的列表，其中每個節(jié)點(diǎn)表示為 [coefficient, power] 。例如，多項(xiàng)式 5x³ + 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" 項(xiàng)。示例 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

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;elsecur->next = poly2;return temp->next;} };

88 ms 37.8 MB C++

---

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

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1634. 求两个多项式链表的和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。