leetcode刷题： 002 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

首先使用链表实现等长无进位的求和，即实现 (1 —> 2 -> 3) + (1 -> 2 -> 3)=（2 -> 3 -> 6）

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 struct ListNode {
 6      int val;
 7      ListNode *next;
 8      ListNode(int x) : val(x), next(NULL) {}
 9 };
10 
11 
12 class Solution {
13 public:
14     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
15         
16         int val1 = 0, val2 = 0;
17         
18         ListNode *l = NULL;
19         ListNode *l_end = NULL;
20         ListNode *l_new = NULL;
21         
22         val1 = l1->val;
23         val2 = l2->val;
24         l1 = l1->next;
25         l2 = l2->next;
26         l_new = (ListNode *)new ListNode((val1 + val2) % 10);
27         l_new->next = NULL;
28         l = l_new;
29         l_end = l;
30         while (l1 != NULL || l2 != NULL){
31 
32                 val1 = l1->val;
33                 val2 = l2->val;
34                 l1 = l1->next;
35                 l2 = l2->next;
36 
37             l_new = (ListNode *)new ListNode((val1 + val2)%10);
38             l_new->next = NULL;
39 
40             l_end->next = l_new;
41             l_end = l_new;
42         }
43 
44         return l;
45 
46     }
47 };
48 
49 int main()
50 {
51     ListNode *l1, *l2;
52     ListNode *l;
53     l1 = (ListNode *)new ListNode(1);
54     l2 = (ListNode *)new ListNode(1);
55     l1->next = (ListNode *)new ListNode(2);
56     l2->next = (ListNode *)new ListNode(2);
57     l1->next->next = (ListNode *)new ListNode(3);
58     l2->next->next = (ListNode *)new ListNode(3);
59     Solution s;
60     l = s.addTwoNumbers(l1, l2);
61     while (l != NULL){
62         cout << l->val << endl;
63         l = l->next;
64     }
65     while (1);
66 }

运行结果：

然后实现不等长无进位的求和，即实现 (1 —> 2 -> 3) + (1)=（2 -> 2 -> 3）

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 struct ListNode {
 6      int val;
 7      ListNode *next;
 8      ListNode(int x) : val(x), next(NULL) {}
 9 };
10 
11 
12 class Solution {
13 public:
14     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
15         
16         int val1 = 0, val2 = 0;
17         
18         ListNode *l = NULL;
19         ListNode *l_end = NULL;
20         ListNode *l_new = NULL;
21         
22         val1 = l1->val;
23         val2 = l2->val;
24         l1 = l1->next;
25         l2 = l2->next;
26         l_new = (ListNode *)new ListNode((val1 + val2) % 10);
27         l_new->next = NULL;
28         l = l_new;
29         l_end = l;
30         while (l1 != NULL || l2 != NULL){
31             if (l1 == NULL){
32                 val2 = l2->val;
33                 l2 = l2->next;
34                 val1 = 0;
35             }
36             else if (l2 == NULL){
37                 val1 = l1->val;
38                 l1 = l1->next;
39                 val2 = 0;
40             }
41             else{
42                 val1 = l1->val;
43                 val2 = l2->val;
44                 l1 = l1->next;
45                 l2 = l2->next;
46             }
47             
48             l_new = (ListNode *)new ListNode((val1 + val2)%10);
49             l_new->next = NULL;
50 
51             l_end->next = l_new;
52             l_end = l_new;
53         }
54 
55         return l;
56 
57     }
58 };
59 
60 int main()
61 {
62     ListNode *l1, *l2;
63     ListNode *l;
64     l1 = (ListNode *)new ListNode(1);
65     l2 = (ListNode *)new ListNode(1);
66     l1->next = (ListNode *)new ListNode(2);
67     //l2->next = (ListNode *)new ListNode(2);
68     l1->next->next = (ListNode *)new ListNode(3);
69     //l2->next->next = (ListNode *)new ListNode(3);
70     Solution s;
71     l = s.addTwoNumbers(l1, l2);
72     while (l != NULL){
73         cout << l->val << endl;
74         l = l->next;
75     }
76     while (1);
77 }

运行结果：

最后实现不等长有进位的求和，即实现题目要求（注意最后一位有进位的情况）

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 struct ListNode {
 6      int val;
 7      ListNode *next;
 8      ListNode(int x) : val(x), next(NULL) {}
 9 };
10 
11 class Solution {
12 public:
13     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
14         
15         int val1 = 0, val2 = 0, carry = 0;
16         
17         ListNode *l = NULL;
18         ListNode *l_end = NULL;
19         ListNode *l_new = NULL;
20         
21         val1 = l1->val;
22         val2 = l2->val;
23         l1 = l1->next;
24         l2 = l2->next;
25         l_new = (ListNode *)new ListNode((val1 + val2 + carry) % 10);
26         l_new->next = NULL;
27         l = l_new;
28         carry = (val1 + val2 + carry) / 10;
29         l_end = l;
30         while (l1 != NULL || l2 != NULL){
31             if (l1 == NULL){
32                 val2 = l2->val;
33                 l2 = l2->next;
34                 val1 = 0;
35             }
36             else if (l2 == NULL){
37                 val1 = l1->val;
38                 l1 = l1->next;
39                 val2 = 0;
40             }
41             else{
42                 val1 = l1->val;
43                 val2 = l2->val;
44                 l1 = l1->next;
45                 l2 = l2->next;
46             }
47             
48             l_new = (ListNode *)new ListNode((val1 + val2 + carry)%10);
49             l_new->next = NULL;
50             carry = (val1 + val2 + carry) / 10;
51 
52             l_end->next = l_new;
53             l_end = l_new;
54         }
55         if (carry != 0){
56             l_new = (ListNode *)new ListNode(carry);
57             l_new->next = NULL;
58             l_end->next = l_new;
59             l_end = l_new;
60         }
61         return l;
62 
63     }
64 };
65 
66 int main()
67 {
68     ListNode *l1, *l2;
69     ListNode *l;
70     l1 = (ListNode *)new ListNode(1);
71     l2 = (ListNode *)new ListNode(1);
72     l1->next = (ListNode *)new ListNode(2);
73     l2->next = (ListNode *)new ListNode(9);
74     l1->next->next = (ListNode *)new ListNode(2);
75     l2->next->next = (ListNode *)new ListNode(7);
76     Solution s;
77     l = s.addTwoNumbers(l1, l2);
78     while (l != NULL){
79         cout << l->val << endl;
80         l = l->next;
81     }
82     while (1);
83 }

运行结果：

因为是一边学C++，一边刷leetcode，所以有什么问题，十分感谢您能指点。