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