算法--力扣2. 兩數(shù)相加
題目：
給你兩個(gè) 非空 的鏈表，表示兩個(gè)非負(fù)的整數(shù)。它們每位數(shù)字都是按照 逆序 的方式存儲的，并且每個(gè)節(jié)點(diǎn)只能存儲 一位 數(shù)字。
請你將兩個(gè)數(shù)相加，并以相同形式返回一個(gè)表示和的鏈表。
你可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會以 0 開頭。
思路：這題算是中等難度的。給個(gè)簡單思路：
想象你有兩個(gè)倒著寫的數(shù)字，比如 243 和 564。它們倒著寫成了鏈表形式：
我們要做的是把這兩個(gè)數(shù)字相加，得到 807，然后倒著寫成鏈表：
步驟
-
定義節(jié)點(diǎn)和鏈表：每個(gè)節(jié)點(diǎn)只包含一個(gè)數(shù)字和一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針。我們用
ListNode這個(gè)結(jié)構(gòu)來表示節(jié)點(diǎn)。 -
創(chuàng)建結(jié)果鏈表：我們用一個(gè)虛擬的頭節(jié)點(diǎn)（dummyHead）開始，這樣可以方便處理鏈表的頭部。這個(gè)虛擬頭節(jié)點(diǎn)的值設(shè)為0，它的下一個(gè)節(jié)點(diǎn)是我們實(shí)際的結(jié)果鏈表的頭。
-
遍歷兩個(gè)鏈表：我們從鏈表的頭部開始，每一位分別相加。如果有進(jìn)位（和大于10），就記錄下來，下一位相加的時(shí)候加上這個(gè)進(jìn)位。
-
處理進(jìn)位：如果最后一位相加完還有進(jìn)位，需要在結(jié)果鏈表的最后加一個(gè)新的節(jié)點(diǎn)，值為1。
/** * 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 dummyHead = new ListNode(0); let current = dummyHead; let carry = 0; while (l1 !== null || l2 !== null) { let x = (l1 !== null) ? l1.val : 0; let y = (l2 !== null) ? l2.val : 0; let sum = carry + x + y; carry = Math.floor(sum / 10); current.next = new ListNode(sum % 10); current = current.next; if (l1 !== null) l1 = l1.next; if (l2 !== null) l2 = l2.next; } if (carry > 0) { current.next = new ListNode(carry); } return dummyHead.next; };
浙公網(wǎng)安備 33010602011771號