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]
  

Constraints:

• The number of node s 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.

解题思路：

这道题虽然难度中等，但是没有什么特别的解法，就是遍历两个linked list， 时间复杂度 为O(n)。

主要考虑几个细节：

1. 进位，当相加的结果大于等于10时，需要进位。
2. 相加结果大于等于10时，保留个位的数字，%10。
3. 两个linked list长度有可能不等。
4. 两个 链表 都遍历结束时，还要看看最后的节点是否有进位，如果有进位需要在new一个node，把进位值存入node。

 /**
 * 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) {
        if (l1==null && l2==null) {
            return null;
        }
        
        if (l1==null) {
            return l2;
        }
        
        if (l2==null) {
            return l1;
        }
        
        ListNode node = new ListNode(0);
        ListNode ln = node;
        boolean flag =  False ;
        
        while(l1 != null) {
            int num = 0;
            num += l1.val;
            if (l2 != null) {
                num += l2.val;
                l2 = l2.next;
            }
            
            if (flag) {
                num += 1;
            }
            
            if (num >= 10) {
                num = num - 10;
                flag = true;
            } else {
                flag = false;
            }
            
            ListNode next = new ListNode(num);
            node.next = next;
            node = next;   
            l1 = l1.next;
        }
        
        while(l2 != null) {
            int num = 0;
            num += l2.val;
            if (flag) {
                num += 1;
            }
            
            if (num >= 10) {
                num = num - 10;
                flag = true;
            } else {
                flag = false;
            }
            
            ListNode next = new ListNode(num);
            node.next = next;
            node = next;
            l2 = l2.next;
        }
        
        if (flag) {
            ListNode next = new ListNode(1);
            node.next = next;
        }
        
        
        return ln.next;
    }
}  

 # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 == None and l2 == None:
            return None
        
        if l1 == None:
            return l2
        
        if l2 == None:
            return l1
        
        ln = ListNode(0, None)
        first = ln
        leading = False
        
        while l1 != None:
            val = 0
            v1 = l1.val
            if l2 != None:
                v2 = l2.val
                val = v1 + v2
                if leading:
                    val += 1
                    leading = False
                if val > 9:
                    leading = True
                    val %= 10

                ln.next = ListNode(val, None)
                ln = ln.next
                l1 = l1.next
                l2 = l2.next
            else:
                val = v1
                if leading:
                    val += 1
                    leading = False
                if val > 9:
                    leading = True
                    val %= 10
            
                ln.next = ListNode(val, None)
                ln = ln.next
                l1 = l1.next
        
        while l2 != None:
            v2 = l2.val
            val = v2
            if leading:
                val += 1
                leading = False
                
            if val > 9:
                leading = True
                val %= 10
            
            ln.next = ListNode(val, None)
            ln = ln.next
            l2 = l2.next
            
        if leading:
            ln.next = ListNode(1, None)
            leading = False
        
        return first.next