Day 17 : Add Two Numbers

这一题题目会给我们两个Linked Lists，分别代表两个非负整数。题目要我们把两个数相加後回传一个新的Linked Lists来代表相加後的和。

题目有说，这两个数在Linked List是以reverse order保存，也就是说Linked List的头（l1的２)代表的是least significant digit(最低有效位数);反之，尾巴（l1的３)就是most significant digit。

Input: l1 = [7,4,3,8], l2 = [5,6,4]

			l1: 7 -> 4 -> 3 -> 8 -> null
read   <----------------反过去l1代表8347

先来暴力的思考这题解法，直觉上我们会去读取l1得到8347，而後读取l2得到465，然後相加得到8812後转换成Linked List输出成2 → 1 → 8 → 8 → null这个方法会是Ｏ(m+n)，其中m是l1的长度，n是l2长度

这种重复的行为外加看到这种会和长度直接有相关的时间复杂度，就会很想要把它缩短在两者之间比较长的那一个，以这个例子来说，我会希望时间复杂度被bound在以l1的长度有关

我们就来直接看有什麽方法来实现吧！

1. 我们需要先建立一个假的node（dummy node），把它的值初始化为0
2. 建立一个pointer代表我们现在所在的位置(current)，用来追踪我们新建立的linklist
3. 建立一个储存是否有进位的变数（carry）
4. 需要两个pointer来追踪我们当下要追踪的l1和l2

一开始我们把两个追踪linked list的指标指向 7 和 5→ 7+5＝12

• 藉由12 % 10 = 2 当作我们要建立新的node的值 ，也就是dummy.next = 2
• 12 / 10 = 1取floor来当作我们的进位carry
  

接着我们继续下一步，currentNode来到２

• 藉由( 4+6 + carry(1))% 10 = 1
• （4+6 + carry(1)）/ 10 = 1
• 建立一个新的node（１）到current.next後，再继续调整current的位置
  
  我们依照上面的方式到l1的8时，我们会发现l2已经没有已经没有数字可以指向，这时候我们需要帮它建立一个value为0的node

最後我们会得到 0 → 2 → 1 → 8 → 8 → null
也就是我们只要把 dummy head後面的linked list回传就会是我们的答案！
这个方式的时间复杂度就可以缩减到Ｏ(max(m,n))，空间复杂度Ｏ(max(m,n))

直接来看程序码吧！

var addTwoNumbers = function (l1, l2) {
  const newHeadPointer = new ListNode(0);
  let current = newHeadPointer;
  let carry = 0;
  let pointerOne = l1;
  let pointerTwo = l2;
  while (pointerOne !== null || pointerTwo !== null || carry !== 0) {
    const valOne = pointerOne !== null ? pointerOne.val : 0;
    const valTwo = pointerTwo !== null ? pointerTwo.val : 0;
    const sumOfVal = valOne + valTwo + carry;

    const newVal = sumOfVal % 10;
    const newNode = new ListNode(newVal);
    current.next = newNode;
    current = newNode;

    carry = Math.floor(sumOfVal / 10);
    pointerOne = pointerOne != null ? pointerOne.next : null;
    pointerTwo = pointerTwo != null ? pointerTwo.next : null;
  }
  return newHeadPointer.next;
};

明日题目预告: 一定要会的二分搜寻 Binary Search