2.兩數相加

給你兩個 非空 的鏈表，表示兩個非負的整數。它們每位數字都是按照 逆序 的方式存儲的，並且每個節點只能存儲 一位 數字。

請你將兩個數相加，並以相同形式返回一個表示和的鏈表。

你可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。

示例 1：

輸入：l1 = [2,4,3], l2 = [5,6,4]
輸出：[7,0,8]
解釋：342 + 465 = 807.

示例 2：

輸入：l1 = [0], l2 = [0]
輸出：[0]

示例 3：

輸入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
輸出：[8,9,9,9,0,0,0,1]

提示：

• 每個鏈表中的節點數在範圍 [1, 100] 內
• 0 <= Node.val <= 9
• 題目數據保證列表表示的數字不含前導零

思路：

1. 首先創建一個啞節點dummy，通過cur指針指向該啞節點，那麼之後該cur指針的操作可用dummy.next來表示最終的鏈表結果
2. 接著當任意一個鏈表不為空的情況下，對這兩個鏈表當前節點的值進行相加，由於要註意到數值相加到10就要進一位的情況，所以要加個變數carry來取整除數和餘數來輔助判斷cur指向的下一個節點的值應該是多少

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let dummy = new ListNode(null),
    cur = dummy,
    carry = 0;
    while(l1 != null || l2 != null){
        const l1Val = (l1!=null) ? l1.val : 0;
        const l2Val = (l2!=null) ? l2.val : 0;
        const sumVal = carry + l1Val + l2Val;
		//取整除數，不僅消除要超過10以上的數值影響，還可以判斷是否要進一位到sumVal
        carry = Math.floor(sumVal/10);
        //取餘數作為鏈表的下一個節點
        cur.next = new ListNode(sumVal % 10);        
        //cur向右移動
        cur = cur.next;
        
        if(l1){
            l1 = l1.next;
        }
        if(l2){
            l2 = l2.next;
        }
        //如果最後溢出1的話，就添加為1的節點即可。
        if(carry>0){
            cur.next=new ListNode(carry);
        }
    }
    return dummy.next;
};

複雜度分析

• 時間複雜度：\(O(\max(m,n))\)，其中 \(m\) 和 \(n\) 分別為兩個鏈表的長度。我們要遍歷兩個鏈表的全部位置，而處理每個位置只需要 \(O(1)\) 的時間。
• 空間複雜度：\(O(1)\)。註意返回值不計入空間複雜度。