# 2.Add Two Numbers <span class='tag' data-diff='medium'></span>
{%hackmd RN5D4nggQRO8wzNqxuvlNw %}

## 題目
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:**

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

## 思路
這一題算是滿有趣的題目，有一點點在仿硬體加法器的味道。題目有幫你先定義好link list的class:

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

首先先初始化結果link list和一個指標，目前都指向同一個物件，還有進位(carry)初始為0。

let ptr = res = new ListNode(),
    carry = 0;

接下來用一個while迴圈，計算目前位置的值與進位，要進到下一個iteration時，把$l_1$、$l_2$都指向他們的next，如果$l_1$、$l_2$都沒有下一位的話，跳離迴圈，否則幫指標建立一下一位，同樣為一個ListNode物件，初始值為當前的進位。
離開迴圈後，如果此時進位不是0，代表結果比$l_1$、$l_2$都還要多出一位，此時就需要再幫指標建立新的node。

while(1){
    ptr.val += ((l1 || new ListNode()).val + (l2 || new ListNode()).val);
    carry = Math.floor(ptr.val / 10);
    ptr.val %= 10;

    if((l1 || new ListNode()).next || (l2 || new ListNode()).next){
       ptr.next = new ListNode(carry);

       ptr = ptr.next;
       l1 = (l1 || new ListNode()).next;
       l2 = (l2 || new ListNode()).next; 
    }
    else break;
}

if(carry) ptr.next = new ListNode(carry);
return res;

由於l1、l2不一定有相同的位數，而且可能差了很多位，為了避免對null物件呼叫next而發生錯誤，每此指向他們next時，需要或運算一個空的ListNode物件，由於$l_1$、$l_2$再`｜|`的前面，只有在他們為`null`時，或運算才會計算。
指標(pointer)通常是在計概才會提到的東西，而且多以C++為例子，所以用javascript寫，常常會不知道變數通常是pass by value還是pass by reference，要再深入一點研究。