題目
給出兩個 非空 的鏈表用來表示兩個非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照 逆序 的方式存儲的井仰，并且它們的每個節(jié)點(diǎn)只能存儲 一位 數(shù)字。
如果破加，我們將這兩個數(shù)相加起來俱恶，則會返回一個新的鏈表來表示它們的和。
您可以假設(shè)除了數(shù)字 0 之外范舀，這兩個數(shù)都不會以 0 開頭合是。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807
解題
C++版本：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int sum = 0;
int flag = 0;
sum = l1->val + l2->val;
if(sum >= 10){
sum = sum - 10;
flag = 1;
}
l1->val = sum;
ListNode* node = new ListNode(0);
if(l1->next != NULL || l2->next != NULL){//至少有一個存在下一個數(shù)
if(l1->next == NULL)
l1->next = node;
if(l2->next == NULL)
l2->next = node;
if(flag==1){
l1->next->val = l1->next->val +1;
flag = 0;
}
addTwoNumbers(l1->next,l2->next);//遞歸
}
else{//都不存在下一個數(shù)
if(flag == 1){
l1->next = new ListNode(1);
flag = 0;
}
}
return l1;
}
};
較慢
C++版本提交
Python3版本：
class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
re = ListNode(0)
r=re
carry=0
while(l1 or l2):
x= l1.val if l1 else 0
y= l2.val if l2 else 0
s=carry+x+y
carry=s//10
r.next=ListNode(s%10)
r=r.next
if(l1!=None):l1=l1.next
if(l2!=None):l2=l2.next
if(carry>0):
r.next=ListNode(1)
return re.next
好像也不快
Python版本提交
