2 Add Two Number

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //思路: 從兩list中讀取每node val, 相加, 並維護進位value, 如最後一個node的value 大於9, 添加新的node 並將新的node val 設為相加後的餘數
        
        //利用carry 變量來儲存進位數, (l1.val + l2.val)%10 是保留的數值, (l1.val + l2.val)/10 是要carry去下一個node的進位數值
        
        // (7/10) 會output 0, (17/10) 會output 1,  所以carry的進位由(value + carry) / 10 表示, 原值的保留由 (value + carry) %10 表示
        
        ListNode head = null;
        ListNode pre = null;
        int carry = 0;
        int digit = 0;
        
        while (l1!=null & l2!=null){
            digit = (l1.val + l2.val + carry) %10;
            carry = (l1.val + l2.val + carry) /10;
            ListNode next_node = new ListNode (digit);  //創造新的node with 新的digit value
            if (head==null)
                head = next_node; //用head去儲存 next_node的位置
            else
                pre.next = next_node; //將pre的下一個node assign為next_node
            pre = next_node;   //用pre去獲得next_node的位置 --> 以便進下next_node的計算
            l1 = l1.next;  //l1 & l2 順移一個node
            l2 = l2.next;
        }
        while (l1!=null){
            digit = (l1.val + carry) %10; //計算
            carry = (l1.val + carry) /10;
            ListNode next_node = new ListNode (digit);
            pre.next = next_node; //pre 順移一node
            pre = next_node;
            l1 = l1.next;
        }
        while (l2!=null){
            digit = (l2.val + carry) %10;
            carry = (l2.val + carry) /10;
            ListNode next_node = new ListNode (digit);
            pre.next = next_node; //pre 順移一node
            pre = next_node;
            l2 = l2.next;
        }
        
        if (carry==1){
            ListNode next_node = new ListNode (carry);
            pre.next = next_node;
        }
        
        return head; //返回虛擬頭結點
    }
}

以下代碼利用dummy head 虛擬頭結點返回head node
首先
ListNode dummy = new ListNode (0); //創造空頭結點
ListNode cur = dummy; //覆制dummy note
cur.next = new_node; //更新下一個node的資料
cur = cur.next; //更新現時結點位置到下一個node
return dummy.next // dummy.next即 return node 1 from node 0 --> node 1 --> node 2 --> node 3 --> null

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //思路: 從兩list中讀取每node val, 相加, 並維護進位value, 如最後一個node的value 大於9, 添加新的node 並將新的node val 設為相加後的餘數
        
        //利用carry 變量來儲存進位數, (l1.val + l2.val)%10 是保留的數值, (l1.val + l2.val)/10 是要carry去下一個node的進位數值
        
        // (7/10) 會output 0, (17/10) 會output 1,  所以carry的進位由(value + carry) / 10 表示, 原值的保留由 (value + carry) %10 表示
        
        ListNode dummy = new ListNode (0);
        ListNode cur = dummy;
        int carry = 0;
        int digit = 0;
        
        while (l1!=null & l2!=null){
            digit = (l1.val + l2.val + carry) %10;
            carry = (l1.val + l2.val + carry) /10;
            ListNode next_node = new ListNode (digit);
            cur.next = next_node;
            cur = cur.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        while (l1!=null){
            digit = (l1.val + carry) %10;
            carry = (l1.val + carry) /10;
            ListNode next_node = new ListNode (digit);
         cur.next = cur_node;
            cur = cur.next;
            l1 = l1.next;
        }
        while (l2!=null){
            digit = (l2.val + carry) %10;
            carry = (l2.val + carry) /10;
            ListNode next_node = new ListNode (digit);
             cur.next = next_node;
            cur = cur.next;
            l2 = l2.next;
        }
        
        if (carry==1){
            ListNode next_node = new ListNode (carry);
            cur.next = next_node;
        }
        
        return dummy.next; //返回虛擬頭結點
    }
}

代碼3
更簡結的代碼, 用while loop 和 if condition 把l1, l2 的node都檢查一次 for each loop,
之後用sum 儲存起和, 如大於10 則 sum = sum -10, 並將carry 變量加1 記錄進位,
最後將剩余的sum值 設為下一個node值 cur.next = New ListNode (sum);
把carry值帶入sum 值 sum = carry;
然後清空carry 值 carry = 0;

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(-1);
        ListNode cur = res;
        int sum = 0;
        int carry = 0;
        while(l1 != null || l2 != null || sum > 0) {
            if(l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            
            if(l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            
            if(sum >= 10) {
                sum -= 10;
                carry += 1;
            }
            
            cur.next = new ListNode(sum);
            cur = cur.next;
            sum = carry;
            carry = 0;
        }
        return res.next;
    }
}