兩數相加
2. 兩數相加
給出兩個 非空 的鏈表用來表示兩個非負的整數，其中，它們各自的位數是按照 逆序 的方式存盤的，并且它們的每個節點只能存盤 一位 數字，
如果，我們將這兩個數相加起來，則會回傳一個新的鏈表來表示它們的和，
您可以假設除了數字 0 之外，這兩個數都不會以 0 開頭，
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/add-two-numbers
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
class Solutuin {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 哨兵節點
ListNode sentinel = new ListNode(0);
// 游標節點
curr = sentinel;
// 進位
int carry = 0
while (l1 != null || l2 != null) {
if (l1 != null) {
carry += l1.val;
l1 = l1.next;
}
if (l2 != null) {
carry += l2.val;
l2 = l2.next;
}
// 當carry大于10的時候需要考慮進位
curr.next = new ListNode(carry % 10);
carry = carry / 10;
curr = curr.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return sentinel.next;
}
}
進階
如果位數是按正序排列的又該如何求解呢？
445. 兩數相加 II
給你兩個 非空 鏈表來代表兩個非負整數，數字最高位位于鏈表開始位置，它們的每個節點只存盤一位數字，將這兩數相加會回傳一個新的鏈表，
你可以假設除了數字 0 之外，這兩個數字都不會以零開頭，
進階：
如果輸入鏈表不能修改該如何處理？換句話說，你不能對串列中的節點進行翻轉，
示例：
輸入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 8 -> 0 -> 7來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/add-two-numbers-ii
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
import java.util.Stack;
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 使用堆疊反轉鏈表
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
while (l1 != null) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.val);
l2 = l2.next;
}
// 哨兵節點
ListNode sentinel = null;
// 進位
int carry = 0;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
// 依次彈堆疊，相加
if (!stack1.isEmpty()) {
carry += stack1.pop();
}
if (!stack2.isEmpty()) {
carry += stack2.pop();
}
// 從個位開始計算, 依次向前，因此新節點應該掛在頭部，采用頭插法
ListNode node = new ListNode(carry % 10);
node.next = sentinel;
// sentinel始終是新鏈表的頭節點
sentinel = node;
// 進位
carry = carry / 10;
}
return sentinel;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/143954.html
標籤：其他