链式A+B 牛客网 程序员面试金典 C++ Python

• 题目描述
• 有两个用链表表示的整数，每个结点包含一个数位。这些数位是反向存放的，也就是个位排在链表的首部。编写函数对这两个整数求和，并用链表形式返回结果。
• 给定两个链表ListNode* A，ListNode* B，请返回A+B的结果(ListNode*)。
• 测试样例：
• {1,2,3},{3,2,1}
• 返回：{4,4,4}

C++

/*
 * struct ListNode {
 *     int val;
 *         struct ListNode *next;
 *             ListNode(int x) : val(x), next(NULL) {}
 *             };*/
class Plus {
public:
// run: 3ms memory:456k
    ListNode* plusAB(ListNode* a, ListNode* b) {
        ListNode* ret = new ListNode(0);
        ListNode* p = ret;
        int j=0;
        while(NULL!=a || NULL!=b || j!=0){
            ListNode* s = new ListNode(0);
            s->val += j;
            if (NULL!=a) s->val += a->val;
            if (NULL!=a) a = a->next;
            if (NULL!=b) s->val += b->val;
            if (NULL!=b) b = b->next;
            if (s->val >= 10) j=1; else j = 0;
            if (s->val >=10) s->val -= 10;
            p = p->next = s;
        }
        ListNode* r = ret->next;
        free(ret);
        return r;
    }

// run:2ms memory:476k
    ListNode* plusAB2(ListNode* a, ListNode* b) {
        ListNode* ret = new ListNode(0);
        ListNode* p = ret;
        int j=0;
        while(NULL!=a || NULL!=b || j!=0){
            ListNode* s = new ListNode(0);
            s->val += j;
            if (NULL!=a) {
                s->val += a->val;
                a = a->next;
            }
            if (NULL!=b) {
                s->val += b->val;
                b = b->next;
            }
            if (s->val >= 10) {
                j=1;
                s->val -= 10;
            }else{
                j=0;
            }
            p->next = s;
            p = p->next;
        }
        ListNode* r = ret->next;
        free(ret);
        return r;
    }

// run:4 memory:608k
    ListNode* plusAB3(ListNode* a, ListNode* b) {
        ListNode* ret = new ListNode(0);
        ListNode* p = ret;
        int j=0;
        while(NULL!=a && NULL!=b){
            ListNode* s = new ListNode(0);
            s->val = a->val + b->val + j;
            if (s->val >= 10){
                j = 1;
                s->val -= 10;
            }else
                j = 0;
            p->next = s;
            p = p->next;
            a = a->next;
            b = b->next;
        }
        while(NULL!=a){
            ListNode* s = new ListNode(0);
            s->val = a->val + j;
            if (s->val >= 10){
                j = 1;
                s->val -= 10;
            }else
                j = 0;
            p->next = s;
            p = p->next;
            a = a->next;
        }
        while(NULL!=b){
            ListNode* s = new ListNode(0);
            s->val = b->val + j;
            if (s->val >= 10){
                j = 1;
                s->val -= 10;
            }else
                j = 0;
            p->next = s;
            p = p->next;
            b = b->next;
        }
        if (1 == j){
            ListNode* s = new ListNode(1);
            p->next = s;
        }
        ListNode* r = ret->next;
        free(ret);
        return r;
    }
};

Python

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Plus:
#run: 27ms memory: 5728k
    def plusAB(slef,a,b):
        ret = ListNode(0)
        p = ret
        j = 0
        while(a or b or j!=0):
            s = ListNode(0)
            s.val += j
            if(a): s.val += a.val
            if(a): a = a.next
            if(b): s.val += b.val
            if(b): b = b.next
            if s.val >= 10: j = 1
            else: j = 0
            if s.val >= 10: s.val -= 10
            p.next = s
            p = p.next
        return ret.next

#run: 37ms memory:5628k
    def plusAB2(slef,a,b):
        ret = ListNode(0)
        p = ret
        j = 0
        while(a or b or j!=0):
            s = ListNode(0)
            s.val += j
            if(a):
                s.val += a.val
                a = a.next
            if(b):
                s.val += b.val
                b = b.next
            if s.val >= 10:
                j = 1
                s.val -= 10
            else:
                j = 0
            p.next = s
            p = p.next
        return ret.next

#run: 22ms memory:5856k
    def plusAB3(self, a, b):
        if None == a: return b
        if None == b: return a
        r = ListNode(0)
        p = r
        j = 0
        while(a and b):
            s = ListNode(0)
            s.val = a.val + b.val + j
            if s.val >= 10:
                j = 1
                s.val -= 10
            else:
                j = 0
            p.next = s
            p = p.next
            a = a.next
            b = b.next
        while(a):
            s = ListNode(0)
            s.val = a.val + j
            if s.val >= 10:
                j = 1
                s.val -= 10
            else:
                j = 0
            p.next = s
            p = p.next
            a = a.next
        while(b):
            s = ListNode(0)
            s.val = b.val + j
            if s.val >= 10:
                j = 1
                s.val -= 10
            else:
                j = 0
            p.next = s
            p = p.next
            b = b.next
        if j == 1:
            s = ListNode(1)
            p.next = s
        return r.next