You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
給定兩個(gè)表示兩個(gè)非負(fù)的鏈表。數(shù)字以逆序存儲枚荣，每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)字。將兩個(gè)數(shù)字相加，以鏈表形式返回和。
Example：
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
解：
intuition（直覺）
算法：
和我們自己在紙上做加法類比漱抓，下面是pseudocode（偽代碼）猿妈。
- 初始化返回鏈表的當(dāng)前結(jié)點(diǎn)為虛設(shè)頭節(jié)點(diǎn)
- 初始化進(jìn)位carry為0
- 初始化p,q分別為l1和l2的頭節(jié)點(diǎn)
- 循環(huán)l1和l2直至兩個(gè)鏈表都結(jié)束。
設(shè)x為p指向的值楣黍。如果p指向l1的尾節(jié)點(diǎn)，設(shè)為0.
設(shè)y為q指向的值棱烂。如果q指向l2的尾節(jié)點(diǎn)租漂，設(shè)為0.
設(shè)sum=x+y+carry.
更新carry=sum/10.
創(chuàng)建新節(jié)點(diǎn)，值為sum%10颊糜，設(shè)為當(dāng)前結(jié)點(diǎn)的下一節(jié)點(diǎn)哩治，前進(jìn)到下一節(jié)點(diǎn)。
p,q都前進(jìn)下一節(jié)點(diǎn)衬鱼。 - 檢查carry是否為1业筏，為1，則添加新的值為1的節(jié)點(diǎn)到返回列表鸟赫。
- 返回虛設(shè)頭的下一節(jié)點(diǎn)蒜胖。
注意一下情形：
| Test case | Explanation |
|---|---|
| l1=[0,1] l2=[0,1,2] |
當(dāng)一個(gè)鏈表比另一個(gè)長 |
| l1=[] l2=[0,1] |
一個(gè)鏈表為空 |
| l1=[9,9] l2=[1] |
結(jié)尾有進(jìn)位 |
代碼如下(C++)：
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int carry =0; ListNode *p=l1, *q=l2, *curr = new ListNode(0); ListNode *dummyhead=curr; while(1){ int x = (p!=NULL)?p->val:0; int y = (q!=NULL)?q->val:0; int sum = x+y+carry; carry = sum/10; curr->val = sum%10; if(p!=NULL) p=p->next; if(q!=NULL) q=q->next; if(p||q){ curr->next = new ListNode(0); curr=curr->next; }else{ if(carry){ curr->next = new ListNode(0); curr=curr->next; } break; } } if(carry>0){ curr->val= carry; } return dummyhead; }
因?yàn)閏++采用指針創(chuàng)建鏈表，在判斷結(jié)束條件的時(shí)候要考慮創(chuàng)建next節(jié)點(diǎn)的條件抛蚤。
復(fù)雜度：
時(shí)間復(fù)雜度：O(max(m,n))
空間復(fù)雜度：O(max(m,n)),最大為max(m,n)+1,用來存儲結(jié)果鏈表台谢。
