leetcode 2. 两数相加

题目详情

题目链接 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

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

我的代码

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* getSum(ListNode* l1, ListNode* l2, int carry) { if (!l1 && !l2 && carry == 0) { return NULL; } auto node = new ListNode(carry); if (l1) { node->val += l1->val; l1 = l1->next; } if (l2) { node->val += l2->val; l2 = l2->next; } carry = 0; if (node->val >= 10) { carry = node->val / 10; node->val %= 10; } node->next = getSum(l1, l2, carry); return node; } ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { return getSum(l1, l2, 0); } };

我的成绩

执行结果：通过 执行用时：60 ms, 在所有 C++ 提交中击败了8.79%的用户 内存消耗：69.9 MB, 在所有 C++ 提交中击败了5.27%的用户

一些想法

本道题我使用的递归。

执行用时为 16 ms 的范例

/** * 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) { int add = 0; ListNode* head = new ListNode(0); ListNode* curr = head; while ((l1 != NULL) || (l2 != NULL)) { int val1 = 0; int val2 = 0; if (l1 != NULL) { val1 = l1->val; l1 = l1->next; } if (l2 != NULL) { val2 = l2->val; l2 = l2->next; } int value = val1 + val2 + add; int temp = value % 10; add = value / 10; curr->next = new ListNode(temp); curr = curr->next; } if (add > 0) { curr->next = new ListNode(add); } return head->next; } };

思考

参见官方解答