Add Two Numbers

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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Analyse:

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
12         ListNode *head = new ListNode(0);
13         ListNode *result = head;
14         
15         int carry = 0;
16         int temp = 0;
17         while(l1 || l2){
18             if(!l1){
19                 temp = l2->val + carry;
20                 l2 = l2->next;
21             }
22             else if(!l2){
23                 temp = l1->val + carry;
24                 l1 = l1->next;
25             }
26             else{
27                 int temp = l1->val + l2->val + carry;
28                 l1 = l1->next;
29                 l2 = l2->next;
30             }
31             carry = temp / 10;
32             result->next = new ListNode(temp % 10);
33             result = result->next;
34         }
35         if(carry){
36             result->next = new ListNode(1);
37             result = result->next;
38         }
39         return head->next;
40     }
41 };

View Code

The above code was wrong but I have not found the reason. OH MY GOD!! The only bug was the "int temp" in line 27!!!!!!! BE CAREFUL!!!! After correction, the run time is 60ms and is more efficient than the last code on this page.

/** * 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) { ListNode *head = new ListNode(0); ListNode *result = head; int carry = 0; int temp = 0; while(l1 || l2){ if(!l1){ temp = l2->val + carry; l2 = l2->next; } else if(!l2){ temp = l1->val + carry; l1 = l1->next; } else{ temp = l1->val + l2->val + carry; //if there is an int before temp, it will go wrong l1 = l1->next; l2 = l2->next; } carry = temp / 10; result->next = new ListNode(temp % 10); result = result->next; } if(carry){ result->next = new ListNode(1); result = result->next; } return head->next; } };

1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) { 12 ListNode *head = new ListNode(0); 13 ListNode *result = head; 14 15 int carry = 0; 16 while(l1 || l2){ 17 int val1 = 0; 18 if(l1){ 19 val1 = l1->val; 20 l1 = l1->next; 21 } 22 23 int val2 = 0; 24 if(l2){ 25 val2 = l2->val; 26 l2 = l2->next; 27 } 28 int temp = val1 + val2 + carry; 29 result->next = new ListNode(temp % 10); 30 carry = temp / 10; 31 result = result->next; 32 } 33 if(carry)result->next = new ListNode(1); 34 35 return head->next; 36 } 37 };

相关推荐