LeetCode 之 JavaScript 解答第二題 —— 兩數相加（Add Two Numbers）

摘要： Time：2019/4/2 Title: ADD Two Numbers Difficulty: medium Author:小鹿 公眾號：一個不甘平凡的碼農。 題目二：ADD Two Numbers You are given two...

Time：2019/4/2

Title: ADD Two Numbers

Difficulty: medium

Author:小鹿

公眾號：一個不甘平凡的碼農。

題目二：ADD Two Numbers

You are given twonon-empty linked lists representing two non-negative integers. The digits are stored inreverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solve:

▉ 演算法思路：

2）多位數加多位數，反轉連結串列轉化整數，如果整數相加，可能會溢位，此方法行不通。
3）直接進行位數運算，兩連結串列每取出一個就做運算，將結果放入到新連結串列中。

▉ 臨界條件：

2）其中一個連結串列為 null。
3）求和運算會出現額外的進位（一般進位與最高位進位兩種情況）。

▉ 步驟：

2）開始遍歷資料，判斷當前結點是否為 null，為 null 就用 0 代替，否則取出數值；
3）求和（加 carray 進位），判斷是否進位？記錄進位值；
4）求模取餘，計算兩位數的各位數儲存到連結串列中，指標向後移動；
5）判斷結點是否為 null，繼續遍歷（如果連結串列 l2 比 l1 短,沒有下一結點只能返回本身下次處理當做 null 處理）
6) 退出 while 迴圈勿忘最高位滿位情況,carray 還存放著 1,所以判斷最高位是否需要進位，存放到連結串列最後

▉ 程式碼實現：

/**
 * 效能分析：
 * 1)遍歷整個連結串列，時間複雜度為 O（n）。
 * 2)需要額外的 n 大小的空間儲存 計算結果結點，空間複雜度為 O(n)。
 */
var addTwoNumbers = function(l1, l2) {
//定義哨兵結點
let head = new ListNode("head");
let current = head;//臨時指標
//儲存計算後的連結串列
let sumNode = head;
//定義進位變數
let carray = 0;
//開始遍歷兩個連結串列取資料，判斷連結串列是否為 null
while(l1 !== null || l2 !== null){
//判斷取資料的連結串列是否為nulL,為 null 就用 0 替換
let num1 = 0;
let num2 = 0;
if(l1 == null){
num1 = 0;
}else{
num1 = l1.val;
}
if(l2 == null){
num2 = 0;
}else{
num2 = l2.val;
}
// let num1 = l1 == null ? 0 : l1.val;
// let num2 = l2 == null ? 0 : l2.val;
//計算取出的兩個數值的和用於判斷是否滿進位，如果滿 10,carray 需要記錄進位,預設為 0
let sum = num1 + num2 + carray;
//判斷是否需要儲存進位值 1
if(sum > 9){
carray = 1;
}else{
carray = 0;
}
//carray = sum > 9 ? 1 : 0;
//將兩數之和相加[取模(取餘運算)]新增到 sumNode 新連結串列中,一次排列
current.next = new ListNode(sum % 10)
//將指標指向下一連結串列結點
current = current.next;
//繼續遍歷連結串列中的資料，判斷下一結點是否為 null
if(l1 !== null){
l1 = l1.next;
}else{
//如果連結串列 l1 比 l2 短,沒有下一結點只能返回本身下次處理當做 null 處理
l1 = l1;
}
if(l2 !== null){
l2 = l2.next;
}else{
//如果連結串列 l2 比 l1 短,沒有下一結點只能返回本身下次處理當做 null 處理
l2 = l2;
}
// l1 為不為 null 才滿足條件
// l1 = l1 ? l1.next : l1;
// l2 = l2 ? l2.next : l2;
}
//最高位滿位情況,carray 還存放著 1,所以判斷最高位是否需要進位
if(carray === 1){
//有哨兵的，所以需要 next 才能存放下一結點
current.next = new ListNode(1);
}
//返回哨兵結點之後的連結串列
return head.next;
}

▉ 程式碼縮減:

var addTwoNumbers = function(l1, l2) {
//定義哨兵結點
let head = new ListNode("head");
let current = head;//臨時指標
//儲存計算後的連結串列
let sumNode = head;
//定義進位變數
let carray = 0;
//開始遍歷兩個連結串列取資料，判斷連結串列是否為 null
while(l1 !== null || l2 !== null){
//判斷取資料的連結串列是否為nulL,為 null 就用 0 替換
let num1 = l1 == null ? 0 : l1.val;
let num2 = l2 == null ? 0 : l2.val;
//計算取出的兩個數值的和用於判斷是否滿進位，如果滿 10,carray 需要記錄進位,預設為 0
let sum = num1 + num2 + carray;
//判斷是否需要儲存進位值 1
if(sum > 9){
carray = 1;
}else{
carray = 0;
}
//carray = sum > 9 ? 1 : 0;
//將兩數之和相加[取模(取餘運算)]新增到 sumNode 新連結串列中,一次排列
current.next = new ListNode(sum % 10)
//將指標指向下一連結串列結點
current = current.next;
//繼續遍歷連結串列中的資料，判斷下一結點是否為 null
l1 為不為 null 才滿足條件
l1 = l1 ? l1.next : l1;
l2 = l2 ? l2.next : l2;
}
//最高位滿位情況,carray 還存放著 1,所以判斷最高位是否需要進位
if(carray === 1){
//有哨兵的，所以需要 next 才能存放下一結點
current.next = new ListNode(1);
}
//返回哨兵結點之後的連結串列
return head.next;
}

▉ 總結：需要注意幾點。

▉ 擴充套件：

答：

//移動小數點向前一位，得到小數點後一位
個位：a = 123 % 10 = 3
//移動小數點向前兩位，得到小數點後兩位，除以10取整
十位：b= parseInt((123 % 100) / 10)
//移動小數點向前三位，得到小數點後三位，除以100取整
百位:：c = parseInt((123 % 1000) / 100)
//依次類推.....

歡迎關注我個人公眾號：「一個不甘平凡的碼農」，記錄了自己一路自學程式設計的故事。

LeetCode 其他題目解析，請關注我Github：https://github.com/luxiangqia...