2.兩數(shù)相加

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

英吉沙網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)！從網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、響應(yīng)式網(wǎng)站開發(fā)等網(wǎng)站項(xiàng)目制作，到程序開發(fā)，運(yùn)營維護(hù)。創(chuàng)新互聯(lián)于2013年創(chuàng)立到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)。

請(qǐng)你將兩個(gè)數(shù)相加，并以相同形式返回一個(gè)表示和的鏈表。

你可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會(huì)以 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]

提示：

每個(gè)鏈表中的節(jié)點(diǎn)數(shù)在范圍 [1, 100] 內(nèi)
0 <= Node.val <= 9
題目數(shù)據(jù)保證列表表示的數(shù)字不含前導(dǎo)零

思路：

首先創(chuàng)建一個(gè)啞節(jié)點(diǎn)dummy，通過cur指針指向該啞節(jié)點(diǎn)，那么之后該cur指針的操作可用dummy.next來表示最終的鏈表結(jié)果
接著當(dāng)任意一個(gè)鏈表不為空的情況下，對(duì)這兩個(gè)鏈表當(dāng)前節(jié)點(diǎn)的值進(jìn)行相加，由于要注意到數(shù)值相加到10就要進(jìn)一位的情況，所以要加個(gè)變量carry來取整除數(shù)和余數(shù)來輔助判斷cur指向的下一個(gè)節(jié)點(diǎn)的值應(yīng)該是多少

/**
 * 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;
		//取整除數(shù)，不僅消除要超過10以上的數(shù)值影響，還可以判斷是否要進(jìn)一位到sumVal
        carry = Math.floor(sumVal/10);
        //取余數(shù)作為鏈表的下一個(gè)節(jié)點(diǎn)
        cur.next = new ListNode(sumVal % 10);        
        //cur向右移動(dòng)
        cur = cur.next;
        
        if(l1){
            l1 = l1.next;
        }
        if(l2){
            l2 = l2.next;
        }
        //如果最后溢出1的話，就添加為1的節(jié)點(diǎn)即可。
        if(carry>0){
            cur.next=new ListNode(carry);
        }
    }
    return dummy.next;
};

復(fù)雜度分析

時(shí)間復(fù)雜度：\(O(\max(m,n))\)，其中 \(m\) 和 \(n\) 分別為兩個(gè)鏈表的長(zhǎng)度。我們要遍歷兩個(gè)鏈表的全部位置，而處理每個(gè)位置只需要 \(O(1)\) 的時(shí)間。
空間復(fù)雜度：\(O(1)\)。注意返回值不計(jì)入空間復(fù)雜度。

名稱欄目：【JS】2.兩數(shù)相加
本文網(wǎng)址：http://fisionsoft.com.cn/article/dsojpog.html

新聞中心

2.兩數(shù)相加

其他資訊