題目來(lái)源于 LeetCode 上第 2 號(hào)問(wèn)題：兩數(shù)相加。題目難度為 Medium，目前通過(guò)率為 33.9% 。

題目描述

給出兩個(gè) 非空 的鏈表用來(lái)表示兩個(gè)非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照 逆序 的方式存儲(chǔ)的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位 數(shù)字。

如果，我們將這兩個(gè)數(shù)相加起來(lái)，則會(huì)返回一個(gè)新的鏈表來(lái)表示它們的和。

您可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會(huì)以 0 開(kāi)頭。

示例：

輸入：(2?->?4?->?3)?+?(5?->?6?->?4)
輸出：7?->?0?->?8
原因：342?+?465?=?807


題目解析

設(shè)立一個(gè)表示進(jìn)位的變量carried，建立一個(gè)新鏈表，把輸入的兩個(gè)鏈表從頭往后同時(shí)處理，每?jī)蓚€(gè)相加，將結(jié)果加上carried后的值作為一個(gè)新節(jié)點(diǎn)到新鏈表后面。

動(dòng)畫(huà)描述

代碼實(shí)現(xiàn)

///?時(shí)間復(fù)雜度:?O(n)
///?空間復(fù)雜度:?O(n)
class?Solution?{
public:
????ListNode*?addTwoNumbers(ListNode*?l1,?ListNode*?l2)?{

????????ListNode?*p1?=?l1,?*p2?=?l2;
????????ListNode?*dummyHead?=?new?ListNode(-1);
????????ListNode*?cur?=?dummyHead;
????????int?carried?=?0;
????????while(p1?||?p2?){
????????????int?a?=?p1???p1->val?:?0;
????????????int?b?=?p2???p2->val?:?0;
????????????cur->next?=?new?ListNode((a?+?b?+?carried)?%?10);
????????????carried?=?(a?+?b?+?carried)?/?10;

????????????cur?=?cur->next;
????????????p1?=?p1???p1->next?:?NULL;
????????????p2?=?p2???p2->next?:?NULL;
????????}

????????cur->next?=?carried???new?ListNode(1)?:?NULL;
????????ListNode*?ret?=?dummyHead->next;
????????delete?dummyHead;
????????return?ret;
????}
};