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ù)字了惰说。首先遍歷兩個(gè)鏈表磨德，將所有數(shù)字壓入棧s1和s2中，建立一個(gè)值為0的節(jié)點(diǎn)吆视，然后開始循環(huán)典挑，如果棧不為空，就將棧頂數(shù)字加入sum中啦吧，然后將res節(jié)點(diǎn)賦值為res%10您觉，然后建立一個(gè)進(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;
}
