0%

LeeCode[2] - 两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

1
2
3
4
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

解法(C语言):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
struct ListNode* head = (struct ListNode *)malloc(sizeof(struct ListNode));
head->next = NULL;
struct ListNode* current = head;
struct ListNode* p = l1;
struct ListNode* q = l2;
//依次遍历,将结果先不进位保存到新链表中
while (p != NULL || q != NULL) {
int value1 = (p == NULL ? 0 : p->val);
int value2 = (q == NULL ? 0 : q->val);
current->val = value1 + value2;
if ((p != NULL && p->next != NULL)|| (q !=NULL && q->next != NULL)) {
current->next = (struct ListNode *)malloc(sizeof(struct ListNode));
current = current->next;
current->next = NULL;
}
if (p != NULL) {
p = p->next;
}
if (q != NULL) {
q = q->next;
}
}

current = head;
//进位处理
while (current != NULL) {
if (current->val >= 10) {
if (current->next == NULL) {
current->next = (struct ListNode *)malloc(sizeof(struct ListNode));
current->next->val = 0;
current->next->next = NULL;
}
current->next->val += current->val / 10;
current->val = current->val % 10;
}
current = current->next;
}

return head;
}