首页 > 代码库 > LeetCode No.2 Add Two Numbers
LeetCode No.2 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
初看这题,就是C1课上学的超长整数加减法。于是思路就很明确了:
cn = (an + bn + carry) % 10
carry = (an + bn + carry) / 10
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) { int carry = 0, cn, tmp; ListNode *c = NULL, *p, *q, *r, *t; p = l1; q = l2; r = c; while (p && q) { tmp = p->val + q->val + carry; cn = tmp % 10; carry = tmp / 10;
// Add t to end of result list. t = new ListNode(cn); if (c == NULL) c = t; else r->next = t; r = t; p = p->next; q = q->next; } t = p ? p : q;
// When p or q is not entirely processed, keep calculating. while (t) { tmp = t->val + carry; cn = tmp % 10; carry = tmp / 10; r->next = new ListNode(cn); r = r->next; t = t->next; }
// Finally, handle case like 99999 + 1 if (carry) { r->next = new ListNode(carry); } return c; }
运行时间比较理想,163ms
LeetCode No.2 Add Two Numbers
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。