題目

給出兩個(gè)非空的鏈表用來(lái)表示兩個(gè)非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照逆序的方式存儲(chǔ)的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲(chǔ)一位數(shù)字。

如果，我們將這兩個(gè)數(shù)相加起來(lái)，則會(huì)返回一個(gè)新的鏈表來(lái)表示它們的和。

您可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會(huì)以 0 開(kāi)頭。

示例

輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

輸出：7 -> 0 -> 8

原因：342 + 465 = 807

思路

思路比較明確，因?yàn)槭悄嫘虻?，我們只要從第一位一直加下去就可以。每次加一位注意結(jié)果有沒(méi)有大于10，大于就在下一位的計(jì)算時(shí)結(jié)果值+1。

考慮最后可能會(huì)進(jìn)一位的情況(即99+1=100)，需要在最后判斷進(jìn)位是否為1，為1則再追加node。

代碼

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode head = new ListNode(-1);
        ListNode cur = head;

        int carry = 0;

        // 循環(huán)，直到兩個(gè)鏈表都到了末尾
        while (l1 != null || l2 != null) {
            // 如果為null，則賦值0
            // 因?yàn)橛锌赡艽嬖趌1為空但l2不為空
            int d1 = l1 == null ? 0 : l1.val;
            int d2 = l2 == null ? 0 : l2.val;

            // 計(jì)算總和，如果總和大于10，將進(jìn)位置為1
            int sum = d1 + d2 + carry;
            carry = sum >= 10 ? 1 : 0;

            // 將sum賦值給cur.next，并向前走一步
            cur.next = new ListNode(sum % 10);
            cur = cur.next;

            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }

            System.out.println(cur.toString());
        }
        // 如果兩個(gè)循環(huán)結(jié)束了而進(jìn)位為1，則增加一位
        if (carry > 0) {
            cur.next = new ListNode(1);
        }
        // 返回開(kāi)始的節(jié)點(diǎn)
        return head.next;
    }

時(shí)間復(fù)雜度

我們這里只走一次循環(huán)，時(shí)間復(fù)雜度為 O(n)。

leetcode最終執(zhí)行時(shí)間為10ms，超過(guò)84.12%的人。