連結清單求和（尾插法）

連結清單求和

題目描述

給定兩個用連結清單表示的整數，每個節點包含一個數位。

這些數位是反向存放的，也就是個位排在連結清單首部。

編寫函數對這兩個整數求和，并用連結清單形式傳回結果。

輸入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295

輸出：2 -> 1 -> 9，即912

題解(java)

class Solution {
   
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //虛拟頭節點(啞結點)
        ListNode dummy = new ListNode(0);
        ListNode temp = dummy;
        //進位
        int carry = 0;
        while(l1!=null || l2!=null || carry>0){
            int i = l1==null? 0 : l1.val;
            int j = l2==null? 0 : l2.val;
            //相加之和(包含進位的)
            int sum = i + j +carry;
            if(sum>=10){
                //尾插法連接配接
                temp.next = new ListNode(sum%10);
            }else{
                temp.next = new ListNode(sum);
            }
            //更新進位的值
            carry = sum / 10;

            temp = temp.next;
            if(l1!=null){
                l1 = l1.next;
            }
            if(l2!=null){
                l2 = l2.next;
            }
        }
        return dummy.next;
    }
}
           

圖示

詳解(尾插法連接配接)

• 1>.簡單來說，該題需要四個變量，一個是 l1 節點的值 i，一個是 l2 節點的值 j，一個是進位數 count，一個是計算總和的值，其中進位數初始化為0。
• 2>.當 i,j,count中隻要有一個不為 null 或 0時，都需要進入周遊，産生新的節點用頭插法連接配接到連結清單中去
• 3>.其中進位數 count = sum/10，新的節點的值分為兩種情況：【1).當sum<10時，temp.next == sum,當 sum >= 10時，需要對sum進行取餘，即temp.next == sum%10】
• 最後傳回新的節點

進階

進階：思考一下，假設這些數位是正向存放的，又該如何解決呢?

示例：

輸入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295

輸出：9 -> 1 -> 2，即912

• 這裡先把原來的兩個連結清單反轉，再采用頭插法連接配接即可

聲明

• 原作者：E.L.E
• <本文章著作權歸作者所有，商業轉載請獲得作者授權，非商業轉載請注明出處>
• <歡迎大家評論>