给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

解法一：

由于链表可能很长，我们不能把链表转换为整数再相加，然后再转成链表，这样可能会发生整数越界。我们可以直接遍历两个链表，对其中一个一个节点值进行相加，然后保存一个进位标记，就像做加法那样，将每一个加法和存入一个节点中，构造一个新的链表。这里我们建了一个头节点便于最后的返回操作。

太长不看版。

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode head = new ListNode(0);

        ListNode l3 = head;

        int tempSum = 0, addSign = 0;

        while (l1 != null && l2 != null) {
            ListNode listNode = new ListNode(0);

            if (addSign == 1) {
                tempSum = l1.val + l2.val + 1;
            } else {
                tempSum = l1.val + l2.val;
            }

            if (tempSum >= 10) {
                addSign = 1;
                listNode.val = tempSum % 10;
            } else {
                addSign = 0;
                listNode.val = tempSum;
            }

            head.next = listNode;

            head = head.next;

            l1 = l1.next;
            l2 = l2.next;
        }

        while (l1 != null) {
            ListNode listNode = new ListNode(0);

            if (addSign == 1) {
                tempSum = l1.val + 1;
            } else {
                tempSum = l1.val;
            }

            if (tempSum >= 10) {
                listNode.val = tempSum % 10;
                addSign = 1;
            } else {
                listNode.val = tempSum;
                addSign = 0;
            }

            head.next = listNode;
            head = head.next;
            l1 = l1.next;
        }

        while (l2 != null) {
            ListNode listNode = new ListNode(0);
            if (addSign == 1) {
                tempSum = l2.val + 1;
            } else {
                tempSum = l2.val;
            }

            if (tempSum >= 10) {
                listNode.val = tempSum % 10;
                addSign = 1;
            } else {
                listNode.val = tempSum;
                addSign = 0;
            }

            head.next = listNode;
            head = head.next;
            l2 = l2.next;
        }

        if (addSign == 1) {
            ListNode listNode = new ListNode(1);
            head.next = listNode;
            head = head.next;
        }

        return l3.next;
    }

精简版。

    public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        int carry = 0;
        
        while (l1 != null || l2 != null) {
            int d1 = l1 == null ? 0 : l1.val;
            int d2 = l2 == null ? 0 : l2.val;
            int sum = d1 + d2 + carry;
            carry = sum >= 10 ? 1 : 0;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (carry == 1) cur.next = new ListNode(1);
        
        return dummy.next;
    }