題目說明

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

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

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

示例：

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

public class AddTwoNumbers {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode head = new ListNode(-1);
        ListNode cur = head;
        int temp = 0;
        while (l1!=null||l2!=null){

            int x = (l1==null)?0:l1.val;
            int y = (l2==null) ? 0:l2.val;

            int sum = x+y+temp;
            temp = sum/10;
            cur.next = new ListNode(sum%10);
            cur = cur.next;
            if(l1!=null){
                l1=l1.next;
            }
            if(l2!=null){
                l2=l2.next;
            }

        }
        if(temp!=0){
            cur.next = new ListNode(temp);
        }
        return head.next;

    }
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}

復(fù)雜度分析

• 時間復(fù)雜度：O(max(m,n))，假設(shè) m 和 n 分別表示 l1 和 l2 的長度，上面的算法最多重復(fù) max(m,n) 次。

• 空間復(fù)雜度：(max(m,n))， 新列表的長度最多為 max(m,n)+1。