本文首發(fā)于公眾號(hào)「五分鐘學(xué)算法」托修，是圖解 LeetCode 系列文章之一挺勿。
個(gè)人網(wǎng)站：https://www.cxyxiaowu.com
題目來(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)畫描述
image
代碼實(shí)現(xiàn)
/// 時(shí)間復(fù)雜度: O(n)
/// 空間復(fù)雜度: O(n)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
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;
}
};
