【題目描述】
You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored inreverseorder, 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è)用鏈表代表的整數(shù)艘刚，其中每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)字。數(shù)字存儲(chǔ)按照在原來整數(shù)中相反的順序丘侠，使得第一個(gè)數(shù)字位于鏈表的開頭。寫出一個(gè)函數(shù)將兩個(gè)整數(shù)相加必尼，用鏈表形式返回和浑劳。
【題目鏈接】
www.lintcode.com/en/problem/add-two-numbers/
【題目解析】
本題要求將以鏈表存儲(chǔ)的兩個(gè)整數(shù)相加，求和的結(jié)果依然存儲(chǔ)在一個(gè)鏈表中荧嵌，最后返回結(jié)果鏈表的頭指針慰枕。
題目的難點(diǎn)在于
1. 兩個(gè)整數(shù)逆序存儲(chǔ)具则，低位向高位有進(jìn)位時(shí)不再是向前而是向后進(jìn)位。
2. 兩個(gè)整數(shù)不一定有相同的位數(shù)具帮，所以遍歷鏈表時(shí)要判斷是否遍歷結(jié)束博肋，如果結(jié)束，就將其相應(yīng)位置為0蜂厅。
3. 兩個(gè)整數(shù)的最高位相加可能產(chǎn)生進(jìn)位匪凡。
綜上考慮，應(yīng)創(chuàng)建一個(gè)新的鏈表掘猿，其頭節(jié)點(diǎn)為head,指向其的頭指針為p,用carry表示對應(yīng)位相加后的進(jìn)位病游，sum表示相加后結(jié)果。
sum等于兩個(gè)整數(shù)對應(yīng)位相加再加上低位進(jìn)位稠通，sum向高位的進(jìn)位carry = sum / 10衬衬，此時(shí)結(jié)果鏈表新增一個(gè)節(jié)點(diǎn)，其val = sum % 10即p->next = new ListNode(sum % 10)改橘。這樣便完成了一次加法和進(jìn)位操作滋尉，結(jié)果鏈表和兩個(gè)存儲(chǔ)整數(shù)的鏈表的指針向后移動(dòng)一位，重復(fù)之前的加法和進(jìn)位操作唧龄，直到兩個(gè)整數(shù)遍歷結(jié)束且不存在進(jìn)位兼砖。
【參考答案】
