【題目描述】
You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in forward order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
假定用一個(gè)鏈表表示兩個(gè)數(shù)血久，其中每個(gè)節(jié)點(diǎn)僅包含一個(gè)數(shù)字炸卑。假設(shè)這兩個(gè)數(shù)的數(shù)字順序排列牙言，請(qǐng)?jiān)O(shè)計(jì)一種方法將兩個(gè)數(shù)相加棠耕，并將其結(jié)果表現(xiàn)為鏈表的形式。
【題目鏈接】
www.lintcode.com/en/problem/add-two-numbers-ii/
【題目解析】
我們看到這道題的最高位在鏈表首位置，可以看一些不修改鏈表順序的方法。
由于加法需要從最低位開(kāi)始運(yùn)算，而最低位在鏈表末尾弥锄，鏈表只能從前往后遍歷，沒(méi)法取到前面的元素，那怎么辦呢籽暇？我們可以利用棧來(lái)保存所有的元素温治，然后利用棧的后進(jìn)先出的特點(diǎn)就可以從后往前取數(shù)字了，我們首先遍歷兩個(gè)鏈表图仓，將所有數(shù)字分別壓入兩個(gè)棧s1和s2中罐盔，我們建立一個(gè)值為0的res節(jié)點(diǎn)，然后開(kāi)始循環(huán)救崔，如果棧不為空惶看，則將棧頂數(shù)字加入sum中，然后將res節(jié)點(diǎn)值賦為sum%10六孵，然后新建一個(gè)進(jìn)位節(jié)點(diǎn)head纬黎，賦值為sum/10，如果沒(méi)有進(jìn)位劫窒，那么就是0本今，然后我們head后面連上res，將res指向head主巍，這樣循環(huán)退出后冠息，我們只要看res的值是否為0，為0返回res->next孕索，不為0則返回res即可逛艰。
【參考答案】
