题目：给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
可以假设除了数字 0 之外，这两个数字都不会以零开头。
思路：若直接将链表中的数保存到数组中再相加，会出现越界的问题。应将两链表反转后再逐位享价，将进位保存起来。相加的结果保存到新链表的节点上，最后再将链表反转

/**
 * 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 reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        ListNode newList = new ListNode();
        ListNode pre = newList;
        int carry = 0;
        while(l1 !=null || l2!=null){
            int sum = (l1 == null ? 0:l1.val) + (l2 == null ? 0:l2.val)+carry;
            carry = sum>=10 ? 1 : 0;
            sum = sum>=10 ? sum-10:sum;//sum>=10的情况
            pre.next = new ListNode(sum);
            pre = pre.next;//每次相加后，pre指针也要向后移
            l1 = l1==null ? null:l1.next;
            l2 = l2==null ? null:l2.next;

        }
        if(carry>0){
            pre.next = new ListNode(carry);//最后一位相加后还有进位
        }
        return reverseList(newList.next);//最后结果再反转
    }
}