给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 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; }
|