- 难度：
中等 - 本题涉及算法：
栈 - 思路：
栈 - 类似题型：
题目 445. 两数相加 II
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7
解题思路
- 使用堆保存链表,保存结果如[1,2,3,4]
- 通过堆的pop方法从尾部依次获取数据
- pop()函数返回栈顶的元素，并且将该栈顶元素出栈。
代码
java
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
while (l1 != null) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.val);
l2 = l2.next;
}
// 很妙的两个地方 carry 的设置 和 carry >0 的判断 🌟🌟🌟🌟🌟
// 记录和大于10时 +1
// carry >0 当大于10 则向前进 1
int carry = 0;
ListNode head = null;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
int sum = carry;
sum += stack1.isEmpty()? 0: stack1.pop();
sum += stack2.isEmpty()? 0: stack2.pop();
ListNode node = new ListNode(sum % 10);
node.next = head;
head = node;
carry = sum / 10;
}
return head;
}
}
python
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
stack1, stack2 = [], []
while l1:
stack1.append(l1.val)
l1 = l1.next
while l2:
stack2.append(l2.val)
l2 = l2.next
ans = None
carry = 0
while stack1 or stack2 or carry != 0:
sumNum = carry
sumNum += 0 if not stack1 else stack1.pop()
sumNum += 0 if not stack2 else stack2.pop()
curlNode = ListNode(sumNum % 10)
curlNode.next = ans
ans = curlNode
carry = sumNum // 10
return ans
PREVIOUS508. 出现次数最多的子树元素和
NEXT409. 最长回文串