Leetcode --Add Two Numbers(Medium)
===

## Description:
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.

### Constrains:
* The number of nodes in each linked list is in the range [1, 100].
* 0 <= Node.val <= 9
* It is guaranteed that the list represents a number that does not have leading zeros.

### Example:
**Input** Linked list l1 = [2,4,3]
**Input** Linked list l2 = [5,6,4]
**Output** Linked list = [7,0,8]
**Explanation**: 342 + 465 = 807

*Note* :Linked list以反向擺放,要求輸入相加後輸出.

---

## Solution:
給一個進位bit,個別相加後再加上進位,最後考慮最後一個是否進位,若有則給新的list.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry =0;
        ListNode l3 = new ListNode();
        ListNode be = l3 ;
        while(l1 !=null || l2 !=null)
        {
            if(l1 !=null && l2 !=null)
            {
                int p = carry + l1.val + l2.val;
                 
                carry =0;
                
                if(p>=10)
                    carry =1;
                 p %= 10;
                be.val = p;
               
                if(l1.next != null || l2.next !=null)
                {
                   be.next = new ListNode();
                   be =be.next; 
                }

                l1 =l1.next;
                l2 =l2.next;
            }
            else if(l1 !=null)
            {   int p = carry + l1.val ;
                 
                carry =0;
                
                if(p>=10)
                    carry =1;
                 p %= 10;
                be.val = p;
                if(l1.next != null )
                {
                   be.next = new ListNode();
                   be =be.next; 
                }

                l1 =l1.next;
               
            }
            else
            {
               int p = carry+l2.val;
                 
                carry =0;
                
                if(p>=10)
                    carry =1;
                 p %= 10;
                be.val = p;
                if(l2.next != null )
                {
                   be.next = new ListNode();
                   be =be.next; 
                }
                
                l2 =l2.next;
            }
            
        }
        if(carry ==1 )
            be.next = new ListNode(carry);
        
        return l3;
    }
}

**line 15 :** 給一個指標be去操作linked list讓head不會跑掉
**line 18,38,56 :** 分三個case,==1.== l1,l2都未空, ==2.== l1未空,l2空 , ==3.== l1空,l2未空
**line 29 :** 如果l1,l2尚未空再新增list,避免新增出空的list而未使用.
**line 76 :** 對最後一bit若還要進位,則多新增一位list

### Submissions on Leetcode

Runtime: **3 ms** , faster than **11.23%** of Java online submissions for Add Two Numbers.
Memory Usage: **44.4 MB** , less than **5.01%** of Java online submissions for Add Two Numbers.

## Complexity analysis

要遍歷所有list.
### => ==O(max(l1.size,l2.size))==

## Conclusion

再判斷l1,l2是否為空的地方還可以寫更少,還有加上carry的條件,因為不能加null所以分成很多case,多設置一個empty list初值設為0就可以做加法,使速度上升.

參考解答: Reference trysingtime on leetcode
Runtime: **2 ms** , faster than **98.80%** of Java online submissions for Add Two Numbers.
Memory Usage: **41.3 MB** , less than **100.00%** of Java online submissions for Add Two Numbers.

  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode emptyNode = new ListNode(0);
        ListNode currentNode = new ListNode(0);
        ListNode result = currentNode;
        while (emptyNode != l1 || emptyNode != l2) {
            int sum = l1.val + l2.val + carry;
            carry = sum / 10;
            currentNode = (currentNode.next = new ListNode(sum %= 10));
            l1 = null != l1.next ? l1.next : emptyNode;
            l2 = null != l2.next ? l2.next : emptyNode;
        }
        if (carry == 1)
            currentNode.next = new ListNode(carry);
        return result.next;
    }

line 9 : 等同於

currentNode.next = new ListNode(sum %= 10);
currentNode = currentNode.next;

###### tags: `Leetcode` `Medium` `LinkedList`