主題

[LeetCode C#] 2. Add Two Numbers - Linked List

帥氣跳蚤蛋 | 2021-07-11 22:31:35 | 巴幣 0 | 人氣 133

難度: 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不輸出,由下一個開始;
            }
        }

創作回應

相關創作

更多創作