JS 445. Add Two Numbers II(链表相加，高位在前)

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的拓展，这道题的最高位在链表首位，如果把链表翻转一下就和之前的题目一样了，这里采用不修改链表顺序的方法。由于加法需要从最低位开始运算，而最低位在链表末尾，链表只能从前往后遍历，没法渠道前面的元素，那就可以利用栈来保存所有的元素，然后利用栈的先进后出的特点就可以从后往前取数字了。首先遍历两个链表，将所有数字压入栈s1和s2中，建立一个值为0的节点，然后开始循环，如果栈不为空，就将栈顶数字加入sum中，然后将res节点赋值为res%10，然后建立一个进位节点，赋值为Math.floor(sum/10)，如果没有进位，那么就是0。然后我们head节点后面连上res，将res指向head，这样循环推出后，只要看res的值是否为0，为0就返回res.next，不为0则返回res即可。
???空间复杂度超了，
还有就是js是不是没有堆栈，可以直接存数组吗？然后用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;  
}