You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

思路：

是I的拓展，這道題的最高位在鏈表首位，如果把鏈表翻轉(zhuǎn)一下就和之前的題目一樣了，這里采用不修改鏈表順序的方法。由于加法需要從最低位開始運(yùn)算，而最低位在鏈表末尾，鏈表只能從前往后遍歷，沒法渠道前面的元素，那就可以利用棧來保存所有的元素，然后利用棧的先進(jìn)后出的特點(diǎn)就可以從后往前取數(shù)字了。首先遍歷兩個鏈表，將所有數(shù)字壓入棧s1和s2中，建立一個值為0的節(jié)點(diǎn)，然后開始循環(huán)，如果棧不為空，就將棧頂數(shù)字加入sum中，然后將res節(jié)點(diǎn)賦值為res%10，然后建立一個進(jìn)位節(jié)點(diǎn)，賦值為Math.floor(sum/10)，如果沒有進(jìn)位，那么就是0。然后我們head節(jié)點(diǎn)后面連上res，將res指向head，這樣循環(huán)推出后，只要看res的值是否為0，為0就返回res.next，不為0則返回res即可。
???空間復(fù)雜度超了，
還有就是js是不是沒有堆棧，可以直接存數(shù)組嗎？然后用pop和push模擬棧

var addTwoNumbers = function(l1, l2) {
    var s1=[],s2=[];
    while(l1){
        s1.push(l1.val);
        l1=l1.next;
    }
    while(l2){
        s2.push(l2.val);
    }
    var sum=0;
    var res=new ListNode(0);
    while( !s1.length || !s2.length ){
        if(!s1.length){
            sum+=s1.pop();
        }
        if(!s2.length){
            sum+=s2.pop();
        }
        res.val=sum%10;
        var head=new ListNode(Math.floor(sum/10));
        head.next=res;
        res=head;
        sum=Math.floor(sum/10);
    }
    return res.val===0? res.next:res;  
}