首页 > 代码库 > 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课上学的超长整数加减法。于是思路就很明确了:

c= (a+ bn + carry) % 10

carry = (a+ 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