上次编辑到这里，代码来自缓存 点击恢复默认模板
/**
* 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) {
}
};
cpp 解法, 执行用时: 88 ms, 内存消耗: 38.2 MB, 提交时间: 2023-10-17 17:41:12
/**
* 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* p = new PolyNode();
PolyNode* head = p;
while (poly1 && poly2) {
if (poly1->power == poly2->power) {
poly1->coefficient += poly2->coefficient;
if (poly1->coefficient!=0) {
p->next=poly1;
poly1 = poly1->next;
poly2 = poly2->next;
} else {
poly1 = poly1->next;
poly2 = poly2->next;
continue;
}
} else if (poly1->power > poly2->power) {
p->next = poly1;
poly1 = poly1->next;
} else {
p->next = poly2;
poly2 = poly2->next;
}
p=p->next;
}
if (poly1 == nullptr)
p->next = poly2;
else
p->next = poly1;
return head->next;
}
// 递归
PolyNode* addPoly1(PolyNode* poly1, PolyNode* poly2) {
if (!poly1 || !poly2) return max(poly1, poly2);
if (poly1->power == poly2->power) {
poly1->next = addPoly1(poly1->next, poly2->next);
return (poly1->coefficient += poly2->coefficient) ? poly1 : poly1->next;
}
auto [a, b] = minmax(poly1, poly2, [](auto&& a, auto&& b) { return a->power < b->power; });
b->next = addPoly1(a, b->next);
return b;
}
};
javascript 解法, 执行用时: 124 ms, 内存消耗: 55.5 MB, 提交时间: 2023-10-17 17:40:45
/**
* Definition for polynomial singly-linked list.
* function PolyNode(x=0, y=0, next=null) {
* this.coefficient = x;
* this.power = y;
* this.next = next;
* }
*/
/**
* @param {PolyNode} poly1
* @param {PolyNode} poly2
* @return {PolyNode}
*/
var addPoly = function(poly1, poly2) {
let dummy = new PolyNode(), fast = dummy
while(poly1 && poly2){
if(poly1.power === poly2.power){
let sum = poly1.coefficient + poly2.coefficient
if(sum !== 0) fast = fast.next = new PolyNode(sum, poly1.power)
poly1 = poly1.next
poly2 = poly2.next
}else if(poly1.power > poly2.power){
fast = fast.next = poly1
poly1 = poly1.next
}else {
fast = fast.next = poly2
poly2 = poly2.next
}
}
fast.next = null
if(poly1 || poly2) fast.next = poly1 || poly2
return dummy.next
};
python3 解法, 执行用时: 484 ms, 内存消耗: 27.2 MB, 提交时间: 2023-10-17 17:33:25
class Solution:
# 双指针模拟
def addPoly(self, poly1: 'PolyNode', poly2: 'PolyNode') -> 'PolyNode':
p1, p2, ans_tail = poly1, poly2, None
ans = []
while p1 or p2:
if p1 == None or (p2 and p2.power > p1.power):
cur_coff, cur_pow = p2.coefficient, p2.power
p2 = p2.next
elif p2 == None or (p1 and p1.power > p2.power):
cur_coff, cur_pow = p1.coefficient, p1.power
p1 = p1.next
else:
cur_pow, cur_coff = p1.power, p1.coefficient + p2.coefficient
p1, p2 = p1.next, p2.next
if cur_coff != 0:
newNode = PolyNode(cur_coff, cur_pow, None)
if not ans:
ans, ans_tail = newNode, newNode
else:
ans_tail.next = newNode
ans_tail = ans_tail.next
return ans
# 基于字典
def addPoly(self, poly1: 'PolyNode', poly2: 'PolyNode') -> 'PolyNode':
record = defaultdict(int)
def traversalNode(head: 'PolyNode'):
while head:
a,b = head.coefficient,head.power
record[head.power] += a
head = head.next
traversalNode(poly1)
traversalNode(poly2)
ans = PolyNode()
head = ans
for each in sorted(record.keys(),reverse = True):
if record[each] != 0:
new = PolyNode(record[each],each)
head.next = new
head = head.next
return ans.next
java 解法, 执行用时: 1 ms, 内存消耗: 50.2 MB, 提交时间: 2023-10-17 17:30:02
/**
* Definition for polynomial singly-linked list.
* 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 addPoly(PolyNode l, PolyNode r) {
if (l == null) return r;
if (r == null) return l;
if (l.power == r.power) {
l.coefficient += r.coefficient;
if (l.coefficient == 0) return addPoly(l.next, r.next);
l.next = addPoly(l.next, r.next);
return l;
}else if (l.power > r.power) {
l.next = addPoly(l.next, r);
return l;
} else {
r.next = addPoly(l, r.next);
return r;
}
}
// 非递归
public PolyNode addPoly2(PolyNode poly1, PolyNode poly2) {
if(poly1 == null) return poly2;
if(poly2 == null) return poly1;
PolyNode dummyNode = new PolyNode(0, 0);
PolyNode cur = dummyNode;
PolyNode cur1 = poly1, cur2 = poly2;
while(cur1 != null && cur2 != null) {
if(cur1.power > cur2.power) {
cur.next = new PolyNode(cur1.coefficient, cur1.power);
cur1 = cur1.next;
} else if(cur1.power < cur2.power) {
cur.next = new PolyNode(cur2.coefficient, cur2.power);
cur2 = cur2.next;
} else {
int num = cur1.coefficient + cur2.coefficient;
if(num != 0) {
cur.next = new PolyNode(num, cur1.power);
cur1 = cur1.next;
cur2 = cur2.next;
} else {
cur1 = cur1.next;
cur2 = cur2.next;
continue;
}
}
cur = cur.next;
}
if(cur1 != null) {
cur.next = cur1;
}
if(cur2 != null) {
cur.next = cur2;
}
return dummyNode.next;
}
}
