這一題題目會給我們兩個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