給定兩個非空鏈表來表示兩個非負整數(shù)。位數(shù)按照逆序方式存儲，它們的每個節(jié)點只存儲單個數(shù)字。將兩數(shù)相加返回一個新的鏈表。

你可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)字都不會以零開頭。

示例：

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

解法一：

由于鏈表可能很長，我們不能把鏈表轉(zhuǎn)換為整數(shù)再相加，然后再轉(zhuǎn)成鏈表，這樣可能會發(fā)生整數(shù)越界。我們可以直接遍歷兩個鏈表，對其中一個一個節(jié)點值進行相加，然后保存一個進位標記，就像做加法那樣，將每一個加法和存入一個節(jié)點中，構(gòu)造一個新的鏈表。這里我們建了一個頭節(jié)點便于最后的返回操作。

太長不看版。

    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;
    }