給定兩個非空鏈表來表示兩個非負整數。位數按照逆序方式存儲，它們的每個節點只存儲單個數字。將兩數相加返回一個新的鏈表。
你可以假設除了數字 0 之外，這兩個數字都不會以零開頭。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 輸出：7 -> 0 -> 8 原因：342 + 465 = 807
解題思路：我先開始的思路是，再創建一個返回鏈表，然后將兩個數的和放到返回鏈表中返回，具體處理的時候，先檢查每一位相加時前面是不是有進位，如果有進位，則在相加的時候加上進位的值，在計算出每一位的和之后，如果和的值小于10，則沒有進位，進位標志位false，進位值不做修改，如果有進位，則進位標志位true，進位值做相應的修改。然后我的初始代碼如下：
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {bool Carry=false;int Carry_Val=0;int temp; struct ListNode *p1,*p2,*Ret_List;p1=(struct ListNode*)malloc(sizeof(struct ListNode));p1->next=NULL;Ret_List=p1;p2=p1;while(l1&&l2){if(Carry){temp=Carry_Val+l1->val+l2->val;if(temp<10){Carry=false;p2->val=temp;}else{Carry=true;p2->val=temp-10;;Carry_Val=temp/10;}}else{temp=l1->val+l2->val;if(temp<10){Carry=false;p2->val=temp;}else{Carry=true;p2->val=temp-10;Carry_Val=temp/10;}}l1=l1->next;l2=l2->next;if(l1||l2){p1=(struct ListNode*)malloc(sizeof(struct ListNode));p1->next=NULL;p2->next=p1;p2=p1;}}while(l1){if(Carry){temp=Carry_Val+l1->val;if(temp<10){Carry=false;p2->val=temp;}else{Carry=true;p2->val=temp-10;Carry_Val=temp/10;}}else{temp=l1->val;if(temp<10){Carry=false;p2->val=temp;}else{Carry=true;p2->val=temp-10;Carry_Val=temp/10;}}l1=l1->next;if(l1){p1=(struct ListNode*)malloc(sizeof(struct ListNode));p1->next=NULL;p2->next=p1;p2=p1;}}while(l2){if(Carry){temp=Carry_Val+l2->val;if(temp<10){Carry=false;p2->val=temp;}else{Carry=true;p2->val=temp-10;Carry_Val=temp/10;}}else{temp=l2->val;if(temp<10){Carry=false;p2->val=temp;}else{Carry=true;p2->val=temp-10;Carry_Val=temp/10;}}l2=l2->next;if(l2){p1=(struct ListNode*)malloc(sizeof(struct ListNode));p1->next=NULL;p2->next=p1;p2=p1;}}if(Carry){p1=(struct ListNode*)malloc(sizeof(struct ListNode));p1->next=NULL;p2->next=p1;p2=p1;p2->val=Carry_Val;}return Ret_List;}struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {int Carry_Val=0;int temp; struct ListNode *p1,*p2,*Ret_List;p1=(struct ListNode*)malloc(sizeof(struct ListNode));p1->next=NULL;Ret_List=p1;p2=p1;while(l1&&l2){temp=l1->val+l2->val+Carry_Val;p2->val=temp%10;Carry_Val=temp/10;l1=l1->next;l2=l2->next;if(l1||l2){p1=(struct ListNode*)malloc(sizeof(struct ListNode));p1->next=NULL;p2->next=p1;p2=p1;}}while(l1){temp=l1->val+Carry_Val;p2->val=temp%10;Carry_Val=temp/10;l1=l1->next;if(l1){p1=(struct ListNode*)malloc(sizeof(struct ListNode));p1->next=NULL;p2->next=p1;p2=p1;}}while(l2){temp=l2->val+Carry_Val;p2->val=temp%10;Carry_Val=temp/10;l2=l2->next;if(l2){p1=(struct ListNode*)malloc(sizeof(struct ListNode));p1->next=NULL;p2->next=p1;p2=p1;}}if(Carry_Val){p1=(struct ListNode*)malloc(sizeof(struct ListNode));p1->next=NULL;p2->next=p1;p2=p1;p2->val=Carry_Val;}return Ret_List;}struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { int Carry_Val=0; int temp; struct ListNode *p1,*p2,*Ret_List; Ret_List=l1; while(l1&&l2){ temp=l1->val+l2->val+Carry_Val; l1->val=temp%10; Carry_Val=temp/10; p2=l1;l1=l1->next; l2=l2->next; } if(!l1){p2->next=l2;l1=p2->next;}while(l1){ temp=l1->val+Carry_Val; l1->val=temp%10; Carry_Val=temp/10;p2=l1;l1=l1->next; } if(Carry_Val){ p1=(struct ListNode*)malloc(sizeof(struct ListNode)); p1->next=NULL; p1->val=Carry_Val; p2->next=p1;} return Ret_List; } 這就很nice了，空間復雜度也極大的降低了。
歡迎留言評論交流。
