PattySung

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

<解題>

因為他是把陣列裡的數字反過來儲存後，再相加，所以我們必須要從第一個節點的值開始處理。
判斷l1, l2值是否處理完畢（為空）->//l1 != null：表示鏈表 l1 還有數字未處理carry > 0：表示存在進位
同時也要用carry值來儲存值，讓下一位數進位與否。


public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode temp = new ListNode(0);
        ListNode result = temp;

        int dummy= 0;
        int carry = 0;
        while (l1!=null || l2!=null || carry>0){ //l1 != null：表示鏈表 l1 還有數字未處理carry > 0：表示存在進位
            if(l1!=null) {
                dummy += l1.val;
                l1 = l1.next;
            }
            if (l2!=null){
                dummy += l2.val;
                l2 = l2.next;
            }
            dummy += carry;

            if (dummy>9){
                dummy -= 10;
                carry =1; //進位
            } else {
                carry=0; //沒進位
            }
            temp.next = new ListNode(dummy);
            temp = temp.next;

            dummy =0;
        }
        return result.next;
    }
}

Time: O(Max(m,n)) Space: O(Max(m,n))

m and n are the size of l1 and l2

<補充>

在寫的時候，自己輸入了數字去驗證


public class Main {
    public static void main(String[] args) {
        ListNode l1 = createLinkedList(new int[] {2,4,3});
        ListNode l2 = createLinkedList(new int[] {5,6,4});

        Solution solution = new Solution();
        ListNode result = solution.addTwoNumbers(l1, l2);

        // 輸出結果鏈表
        printLinkedList(result);
    }

    // 輔助方法，將陣列轉換為鏈表
    private static ListNode createLinkedList(int[] nums) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        for (int num : nums) {
            dummy.next = new ListNode(num);
            dummy = dummy.next;
        }
        return curr.next;
    }

    // 輔助方法，輸出鏈表的值
    private static void printLinkedList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}


public class ListNode {
    int val;
    ListNode next;
    ListNode prev;

    ListNode(int val) {
        this.val = val;
    }
}


public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode temp = new ListNode(0);
        ListNode result = temp;

        int num1 = 0;
        int num2 = 0;

        while (l1 != null || l2 != null || num2 > 0) { //l1 != null：表示鏈表 l1 還有數字未處理num2 > 0：表示存在進位
            if (l1 != null) {
                num1 += l1.val;
                l1 = l1.next;
            }

            if (l2 != null) {
                num1 += l2.val;
                l2 = l2.next;

            }

            num1 += num2;

            if (num1 > 9) {
                num1 -= 10;
                num2 = 1; //進位=1
            } else {
                num2 = 0; //沒進位=0
            }

            temp.next = new ListNode(num1);
            temp = temp.next;

            num1 = 0;
        }

        return result.next;
    }
}

<補充>

condition ? expression1 : expression2 
-> 這個語法表示如果條件為真，則返回表達式1的結果；否則，返回表達式2的結果
和以下相同：
if (condition)
expression1;
else
expression2;

Leetcode-2. Add Two Numbers

<解題>

<補充>

<補充>