没有什么难的问题，纯粹是用来练链表操作和递归的，难得能一口气ac size数据！
1 class Solution {
2 public:
3 ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
4 // Start typing your C/C++ solution below
5 // DO NOT write int main() function
6 ListNode *res = add(l1, l2, false);
7 return res;
8 }
9 ListNode *add(ListNode *l1, ListNode *l2, bool flag) {
10 int carry = 0;
11 bool cflag = false;
12 if (flag) {
13 carry = 1;
14 }
15 if (l1 == NULL && l2 == NULL) {
16 if (!flag) {
17 return NULL;
18 }
19 ListNode *node = new ListNode();
20 node->val = carry;
21 node->next = NULL;
22 return node;
23 }
24 if (l1 == NULL) {
25 ListNode *node = l2;
26 node->val = l2->val + carry;
27 if (node->val >= 10) {
28 node->val -= 10;
29 cflag = true;
30 }
31 node->next = add(NULL, l2->next, cflag);
32 return node;
33 }
34 if (l2 == NULL) {
35 ListNode *node = l1;
36 node->val = l1->val + carry;
37 if (node->val >= 10) {
38 node->val -= 10;
39 cflag = true;
40 }
41 node->next = add(l1->next, NULL, cflag);
42 return node;
43 }
44 ListNode *node = l1;
45 node->val = l1->val + l2->val + carry;
46 if (node->val >= 10) {
47 node->val -= 10;
48 cflag = true;
49 }
50 node->next = add(l1->next, l2->next, cflag);
51 return node;
52 }
53 };
记得之前在waiting list上看到过一个类似的话题，好像叫单链表和love，那个话题中链表所代表的数字是正数，
并且不允许递归，也要求最多扫描链表两次。 当时也没多想，陈立人给出的答案也不是很好。
为了解决这个问题，似乎有人给出了一个非常聪明的答案。
(There is no difficult problem. It is purely used to practice linked list operation and recursion. It is rare to AC size data in one breath!
1 class Solution {
2 public:
3 ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
4 // Start typing your C/C++ solution below
5 // DO NOT write int main() function
6 ListNode *res = add(l1, l2, false);
7 return res;
8 }
9 ListNode *add(ListNode *l1, ListNode *l2, bool flag) {
10 int carry = 0;
11 bool cflag = false;
12 if (flag) {
13 carry = 1;
14 }
15 if (l1 == NULL && l2 == NULL) {
16 if (!flag) {
17 return NULL;
18 }
19 ListNode *node = new ListNode();
20 node->val = carry;
21 node->next = NULL;
22 return node;
23 }
24 if (l1 == NULL) {
25 ListNode *node = l2;
26 node->val = l2->val + carry;
27 if (node->val >= 10) {
28 node->val -= 10;
29 cflag = true;
30 }
31 node->next = add(NULL, l2->next, cflag);
32 return node;
33 }
34 if (l2 == NULL) {
35 ListNode *node = l1;
36 node->val = l1->val + carry;
37 if (node->val >= 10) {
38 node->val -= 10;
39 cflag = true;
40 }
41 node->next = add(l1->next, NULL, cflag);
42 return node;
43 }
44 ListNode *node = l1;
45 node->val = l1->val + l2->val + carry;
46 if (node->val >= 10) {
47 node->val -= 10;
48 cflag = true;
49 }
50 node->next = add(l1->next, l2->next, cflag);
51 return node;
52 }
53 };
I remember seeing a similar topic on the waiting list before, which seems to be called single linked list and love. The number represented by the linked list in that topic is a positive number,
Recursion is not allowed, and it is also required to scan the linked list at most twice. At that time, he didn't think much, and the answer given by Chen Liren was not very good.
In order to solve this problem, it seems that someone has given a very clever answer.
)
|
收藏
