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

链式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

 

转载于:https://www.cnblogs.com/vercont/p/10210301.html

相关资源：JAVA上百实例源码以及开源项目