難度: Medium
===========================================================================
說明:
給予2組正整數資料的linked lists,
每個節點都包含一個數字,該數字是以相反的順序儲存,
將兩組數字相加以相反順序儲存在linked list,並返回結果,
兩組數字的最開頭皆不會有0出現
===========================================================================
測資:
Input: l1 = [2,4,3], l2 = [5,6,4]Output: [7,0,8]
Explanation: 342 + 465 = 807.
===========================================================================
條件限制:
linked list的node數量為1~100
0 <= Node.val <= 9
list沒有開頭為0的數值
===========================================================================
解題:
int32最大值為2,147,483,647
若遍歷完2個list的數值才進行sum的計算會有溢位的風險,
因此要每個位數要個別計算並放入Node中,
1.建立dummy_head作為解答輸出用的ListNode,建立一個temp指標,用於解題串接Node
2.建立sum,分別計算各位數的數值與進位,並放進Node
3.直到遍歷完l1,l2的node,輸出最初的ListNode位置
public class Solution
{
public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
{
int sum = 0;
ListNode dummy_head = new ListNode(0); //初始位置的Linklist
ListNode temp = dummy_head; //指向dummy_head,用於之後的Linklist位移
while(l1!=null || l2!= null) //當l1 or l2的內有數值
{
if(l1!=null)
{
sum += l1.val; //從低位數開始相加
l1 = l1.next;
}
if(l2!=null)
{
sum += l2.val; //低位數相加
l2 = l2.next;
}
temp.next = new ListNode(sum % 10); //先輸出低位數至result的linklist
temp = temp.next; //dummy_head移位
sum /= 10; //計算進位,若有擇留至下一迴圈相加
}
if(sum>0) //若有殘留的進位,則輸出至最後
temp.next = new ListNode(sum % 10);
return dummy_head.next; //開頭無效的數字0不輸出,由下一個開始;
}
}