[LeetCode] 2. Add Two Numbers 刷題筆記
Cathy P
 2021-03-24 21:03:51      

題目

LeetCode 題目連結：https://leetcode.com/problems/add-two-numbers/

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 contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

輸入兩個不為空的 linked lists 代表兩個為非負數的整數，這些數字以反方向儲存，每一個 node 包含一個數字，將兩數相加，並回傳總和的 linked lists。

Example 1:

1
2
3
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

1
2
Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

1
2
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

解題過程

做法：

將l1和l2的.val相加answers裡，溢位的部分直接將answers.next的值加1，然後將l1和l2移到.next，直到l1和l2皆等於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
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 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 answers = new ListNode(0);
  let curNode = answers;
  let isFirst = true;

  while (l1 || l2) {
    if (!isFirst) {
      if (!curNode.next) {
        curNode.next = new ListNode(0);
      }
      curNode = curNode.next;
    } else {
      isFirst = false;
    }

    let sum = curNode.val;
    if (l1) {
      sum += l1.val;
      l1 = l1.next;
    }
    if (l2) {
      sum += l2.val;
      l2 = l2.next;
    }
    if (sum < 10) {
      curNode.val = sum;
    } else {
      curNode.val = sum - 10;
      curNode.next = new ListNode(1);
    }
  }
  return answers;
};

成績

Runtime: 128 ms (排名：89.43%)
Memory Usage: 43.8 MB (排名：85.30%)

心得

很久沒碰 linked lists 了，也沒用 javascript 寫過，一開始一直在想開頭會多一個 0，後來才想到直接回傳.next就可以跳過開頭的 0 了。