Image From LeetCodeImage From LeetCode

今天我們要講解的是 [Add Two Numbers]，這在 LeetCode 算是比較中階的題目，讓我們一起開始吧！

進來之前請先注意，我的方式不一定完全正確，只是依照我自己的理念進行撰寫，所以如果程式上有什麼更好的解法，歡迎提出見解。

這次題目

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse 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

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

自已解法

大略快速看過，上方是透過兩個NodeList進行數字相加，然而NodeList裡面除了取值之外還暗示下一個節點的數字是什麼，看到這個題目第一個想法是想透過遞迴來實作，不過也想了一下大概要怎麼做，其中當你在測試值的時候可以透過console.log來幫助你除錯。

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {};

從上面題目似乎是把數字反轉接著進行累加，但要記得超過 10 時要進行進位，接著我們可以透過l1.val來取得值，然後l1.next來確認是否有下一個數值的資料，首先我們先從累加部分開始，原本遞迴想說獨立成一個Function，但為了加快實驗好整理，所以直接寫在裡面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2, plus = 0) {
  // 進行數字累加，並且確認是否有進位
  var num = l1.val + l2.val + plus;
  var ans; // 最後回傳的結果
  // 重新設定進位數字為0
  plus = 0;
  if (num >= 10) {
    // 如果數值大於0進行進位
    ans = new ListNode(num - 10);
    plus = 1;
  } else {
    ans = new ListNode(num);
  }
};

接著我們要嘗試使用遞迴，假設下一個值不等於null就重複進行呼叫

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2, plus = 0) {
  // 進行數字累加，並且確認是否有進位
  var num = l1.val + l2.val + plus;
  var ans; // 最後回傳的結果
  // 重新設定進位數字為0
  plus = 0;
  if (num >= 10) {
    // 如果數值大於0進行進位
    ans = new ListNode(num - 10);
    plus = 1;
  } else {
    ans = new ListNode(num);
  }

  // 檢查是否有下一個值
  if (l1.next !== null && l2.next !== null) {
    // 遞迴召喚下一次ListNode
    ans.next = addTwoNumbers(l1.next, l2.next, plus);
  }
  return ans;
};

基本上述概念就大致上完成，不過我提交時發生錯誤，他審核結果是帶入以下鍵值，導致我出錯，因為會遇到累加的問題。

1
2
3
Input: (5) + (5)
Output: 0 -> 1
Explanation: 5 + 5 = 10.

這次我們要加入一些修正：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2, plus = 0) {
  // 進行數字累加，並且確認是否有進位
  var num = l1.val + l2.val + plus;
  var ans; // 最後回傳的結果
  // 重新設定進位數字為0
  plus = 0;
  if (num >= 10) {
    // 如果數值大於0進行進位
    ans = new ListNode(num - 10);
    plus = 1;
  } else {
    ans = new ListNode(num);
  }

  // 檢查是否有下一個值
  if (l1.next !== null && l2.next !== null) {
    // 遞迴召喚下一次ListNode
    ans.next = addTwoNumbers(l1.next, l2.next, plus);
  } else if (l1.next === null && l2.next === null && plus === 1) {
    // 避免只有一層出現錯誤
    ans.next = addTwoNumbers(new ListNode(0), new ListNode(0), plus);
  }
  return ans;
};

這樣就能預防因為只有一層但會有累加的問題，但還有一個問題，假設他帶入值是長度不對等似乎會發生錯誤，雖然官方沒有檢查這部分的問題，但我們以防萬一還是加入一下，假設一方遇到null但另一方有值時，我們就給他預設0的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2, plus = 0) {
  // 進行數字累加，並且確認是否有進位
  var num = l1.val + l2.val + plus;
  var ans; // 最後回傳的結果
  // 重新設定進位數字為0
  plus = 0;
  if (num >= 10) {
    // 如果數值大於0進行進位
    ans = new ListNode(num - 10);
    plus = 1;
  } else {
    ans = new ListNode(num);
  }

  // 除果其中一方有值那需要預先給值0，避免錯誤
  if (l1.next === null && l2.next !== null) l1.next = new ListNode(0);
  if (l1.next !== null && l2.next === null) l2.next = new ListNode(0);

  // 檢查是否有下一個值
  if (l1.next !== null && l2.next !== null) {
    // 遞迴召喚下一次ListNode
    ans.next = addTwoNumbers(l1.next, l2.next, plus);
  } else if (l1.next === null && l2.next === null && plus === 1) {
    // 避免只有一層出現錯誤
    ans.next = addTwoNumbers(new ListNode(0), new ListNode(0), plus);
  }
  return ans;
};

實作結果

最後再提交就能得出下面的結果，這道題似乎是考驗你遞回的概念，算是蠻有挑戰性的一題，不過說不定有其他解法？如果有更好的解法歡迎一起討論，我們下一個挑戰見！

Add Two NumbersAdd Two Numbers