将两个反向存储在链表中的整数求和（即整数的个位存放在了链表首部，一位数对应一个节点），返回的结果仍用链表形式。
给定两个链表ListNode* A，ListNode* B，请返回A+B的结果(ListNode*)。
测试样例：
{1,2,3},{3,2,1} 返回：{4,4,4}
[编程题]链式A+B
public static ListNode plusAB(ListNode a, ListNode b) {
// write code here
ListNode resultHead = new ListNode(-1);
ListNode resultCurrent = resultHead;
int addToNextDigit = 0;
while (a != null || b != null || addToNextDigit != 0) {
int aVal = a != null ? a.val : 0;
int bVal = b != null ? b.val : 0;
int sum = aVal + bVal + addToNextDigit;
int nodeDigit = sum % 10;
addToNextDigit = sum / 10;
resultCurrent.next = new ListNode(nodeDigit);
resultCurrent = resultCurrent.next;
a = a != null ? a.next : null;
b = b != null ? b.next : null;
}
return resultHead.next;
}
发表于 2015-07-15 17:01:20
回复(25)
/*可以用此法完成大数加减，乘法也可以（加减乘都是从低位到高位）
除法需要从高位开始到低位*/
public class Plus {
public ListNode plusAB(ListNode a, ListNode b) {
// write code here
if(a == null || b == null){
return null;
}
int add = 0;
ListNode head = new ListNode(-1);
ListNode resCur = head;
ListNode curA = a;
ListNode curB = b;
while(curA != null || curB != null){
if(curA != null && curB !=null){
resCur.next = new ListNode((curA.val+curB.val+add)%10);
resCur = resCur.next;
add = (curA.val+curB.val+add)/10;
curA = curA.next;
curB = curB.next;
}else if(curA != null){
resCur.next = new ListNode((curA.val+add)%10);
resCur = resCur.next;
add = (curA.val+add)/10;
curA = curA.next;
}else{
resCur.next = new ListNode((curB.val+add)%10);
resCur = resCur.next;
add = (curB.val+add)/10;
curB = curB.next;
}
}
if(add > 0){
resCur.next = new ListNode(add);
resCur = resCur.next;
}
return head.next;
}
}
编辑于 2015-08-31 16:47:44
回复(4)
python 解法.
思路很简单，我这种解法根本不用考虑进位和补位这种麻烦问题。
1、先把a和b表示的整数取出来
2.再计算两个数的和
3.把和表示为链表。
class Plus:
def plusAB(self, aHead, bHead):
# resA 和resB中放a和b的所有数字
resA, resB = [], []
while aHead:
resA.append(str(aHead.val))
aHead = aHead.next
while bHead:
resB.append(str(bHead.val))
bHead = bHead.next
# 计算a+b的和
result = str(int("".join(resA[::-1])) + int("".join(resB[::-1])))
#创建一个链表，从个位开始存放。
dummy = ListNode(0)
pre = dummy
for i in result[::-1]:
node = ListNode(int(i))
pre.next = node
pre = pre.next
return dummy.next
编辑于 2017-10-16 11:46:31
回复(1)
public class Plus {
public ListNode plusAB(ListNode a, ListNode b) {
if (a == null) {
return b;
}
if (b == null) {
return a;
}
ListNode p1 = a, p2 = b;
ListNode head = new ListNode(0);
ListNode p = head;
int sum = 0;
while (p1 != null || p2 != null || sum != 0) {
if (p1 != null) {
sum += p1.val;
p1 = p1.next;
}
if (p2 != null) {
sum += p2.val;
p2 = p2.next;
}
p.next = new ListNode(sum % 10);
sum /= 10;
p = p.next;
}
return head.next;
}
}
发表于 2016-09-02 16:43:25
回复(3)
//思路：相加后，结果都放在b中，如果链表a长，则把a剩余的部分连接在b后
class Plus {
public:
ListNode* plusAB(ListNode* a, ListNode* b) {
// write code here
if(a==NULL||b==NULL)
return NULL;
ListNode *head=b;//相加后的结果存放在链表b
int temp=0;//进位标志
int sum=0;//加的和
while(a->next!=NULL&&b->next!=NULL){
//之前这样写 是错误的(检查了好久)
// b->val=(a->val+b->val+temp)%10;
// temp=(a->val+b->val+temp)/10;
sum=a->val+b->val+temp;
b->val=sum%10;
temp=sum/10;
a=a->next;
b=b->next;
}
if(a->next==NULL&&b->next==NULL){//链表等长
sum=a->val+b->val+temp;
b->val=sum%10;
temp=sum/10;
if(temp>0){
ListNode* newnode=new ListNode(temp);
b->next=newnode;
}
return head;
}
if(a->next==NULL&&b->next!=NULL){//链表b较长
sum=a->val+b->val+temp;
b->val=sum%10;
temp=sum/10;
b->next->val+=temp;
return head;
}
if(a->next!=NULL&&b->next==NULL){//链表a较长
sum=a->val+b->val+temp;
b->val=sum%10;
temp=sum/10;
a->next->val+=temp;
b->next=a->next;
return head;
}
}
};
发表于 2015-11-13 15:42:50
回复(2)
用递归的方式时间和空间复杂度更小：
public class Plus {
public ListNode plusAB(ListNode a, ListNode b) {
if (a == null) {
return b;
}
if (b == null) {
return a;
}
return plusAB(a, b, 0);
}
private ListNode plusAB(ListNode a, ListNode b, int sum) {
if (a == null && b == null && sum == 0) {
return null;
}
if (a != null) {
sum += a.val;
}
if (b != null) {
sum += b.val;
}
ListNode node = new ListNode(sum % 10);
node.next = plusAB(a != null ? a.next : null, b != null ? b.next : null, sum / 10);
return node;
}
}
发表于 2017-06-08 10:49:59
回复(3)
//O(n)算法，解析看注释吧
public ListNode plusAB(ListNode a, ListNode b) {
if(a==null||b==null) return null;
ListNode cur=a;
int temp=0;
while(cur!=null){
if(b==null) break;//b链表结束，咱就退出
temp+=cur.val+b.val;//当前位累加
cur.val=temp%10;//a链表存储和
temp=temp/10;//取进位
if(cur.next==null&&b.next!=null) cur.next=new ListNode(0);//a长度没b长就增加长度
if(cur.next==null&&b.next==null&&temp!=0) cur.next=new ListNode(temp);//加到末尾，如果有进位，就增加进位节点
cur=cur.next;
b=b.next;
}
return a;
}
编辑于 2017-05-11 22:11:38
回复(8)
思路很简单也很清晰, 两结点值跟进位相加，满10进位1。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Plus:
def plusAB(self, a, b):
if not a: return b
if not b: return a
carry = 0
head = p = ListNode(-1)
while a and b:
node = ListNode((a.val + b.val + carry)%10)
p.next = node
carry = 1 if (a.val + b.val + carry) >= 10 else 0
a, b, p = a.next, b.next, p.next
tmp = a if a else None
tmp = b if b else tmp
# 是否还有链表未迭代完
while tmp:
node = ListNode((tmp.val + carry)%10)
p.next = node
carry = 1 if (tmp.val + carry >= 10) else 0
p, tmp = p.next, tmp.next
# 是否还有进位
if carry:
node = ListNode(1)
p.next = node
p = p.next
p.next = None
return head.next
发表于 2016-08-02 09:24:34
回复(0)
//详细注释，喜欢的点点赞呀
public static ListNode plusAB(ListNode a, ListNode b) {
ListNode result=new ListNode(-1);//为了等会尾插方便，事先建立一个头结点，用来保存结果的链表
ListNode newHead=result;//为了输出时方便输出（提前用一个节点记录头结点）
int c=0,val1,val2,sum; //c是每一位数字除以10的结果，val1是链表a的节点的值，val2是链表b的节点的值
while(a!=null||b!=null||c!=0){//这里加入c!=0是为了防止加最后一位数时恰好到了10，然后输出的时候不让它漏掉1
//这里的三目表达式是为了防止有一个链表比较短，如果有一个先遍历完了之后后边的位置用0代替直到另一个也遍历完
val1=(a==null?0:a.val);
val2=(b==null?0:b.val);
sum=val1+val2+c; //准备进行进位操作
c=sum/10;
ListNode node=new ListNode(sum%10);
//大于10把大于10的那部分放进去，小于等于10把本来的和放进去
result.next=node;
result=result.next; //result向后移动一位
a=(a==null?null:a.next); //这里是为了防止a==null，然后造成空指针异常
b=(b==null?null:b.next); //同上
}
return newHead.next;//返回事先记录好的节点，跳过那个自己建立的第一个节点输出
}
编辑于 2019-12-04 19:32:25
回复(0)
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Plus {
public ListNode plusAB(ListNode a, ListNode b) {
// write code here
ListNode cc = new ListNode(0);
ListNode c = cc;
int flag = 0;
int val = 0;
int va = 1;
int sum = 0;
int ccc = 0;
while(a != null || b != null || ccc != 0){
val = (a == null ? 0 : a.val);
va = (b == null ? 0 : b.val);
sum = val + va + ccc;
flag = sum % 10;
ccc = sum / 10;
c.next = new ListNode(flag);
c = c.next;
a = (a == null ? null : a.next);
b = (b == null ? null : b.next);
}
c.next = null;
return cc.next;
}
}
发表于 2018-08-28 17:39:21
回复(0)
ListNode* plusAB(ListNode* a, ListNode* b) {
int carry=0;
ListNode *retHead=new ListNode(0);
ListNode *p=retHead;
while(a||b||carry) {
int vala=a?a->val:0;
int valb=b?b->val:0;
int val=(vala+valb+carry)%10;
carry=(vala+valb+carry)/10;
ListNode *tmp=new ListNode(val);
p->next=tmp;
p=p->next;
a=a?a->next:NULL;
b=b?b->next:NULL;
}
p->next=NULL;
return retHead->next;
}
发表于 2015-10-02 11:09:19
回复(1)
public class Plus {
public ListNode plusAB(ListNode a, ListNode b) {
// write code here
if (a == null) return b;
if (b == null) return a;
ListNode pA = a;
ListNode pB = b;
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
int carry = 0;
while (pA != null && pB != null) {
int sum = pA.val + pB.val + carry;
carry = sum / 10;
cur.next = new ListNode(sum % 10);
cur = cur.next;
pA = pA.next;
pB = pB.next;
}
while (pA != null) {
int sum = pA.val + carry;
carry = sum / 10;
cur.next = new ListNode(sum % 10);
cur = cur.next;
pA = pA.next;
}
while (pB != null) {
int sum = pB.val + carry;
carry = sum / 10;
cur.next = new ListNode(sum % 10);
cur = cur.next;
pB = pB.next;
}
if (pA == null && pB == null && carry != 0) {
cur.next = new ListNode(carry);
}
return dummy.next;
}
}
发表于 2019-11-26 09:19:55
回复(0)
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class Plus {
public:
ListNode* plusAB(ListNode* a, ListNode* b) {
ListNode* head =new ListNode(0);
ListNode* cur = head;
int plus = 0;
while(a||b)
{
int num = (a?a->val:0)+(b?b->val:0)+plus;
if(num >= 10)
{
num -= 10;
plus =1;
}
else
plus = 0;
cur->next =new ListNode(num);
cur = cur->next;
if(a)
a =a->next;
if(b)
b=b->next;
}
if(plus)
cur->next =new ListNode(plus);
return head->next;
}
};
发表于 2018-01-21 11:36:42
回复(0)
总结这题的收获，我注释的都是编译不通过的，节点指针赋初值的时候，不要用NULL，
用new （0）更好，同时指针不要简单的用p=p->next,可能会出现各种意外，
反正编译就是不通过。同时也希望大神抽空花点您宝贵的时间，可以给我解释解释
class Plus {
public:
ListNode* plusAB(ListNode* a, ListNode* b) {
// 头结点
ListNode *head =new ListNode(0);//ListNode *head=NULL;
ListNode *p = head;
int mod= 0,sum,x,y;
ListNode *pa = a,*pb = b;
while(pa !=NULL || pb != NULL || mod != 0){
x = (pa == NULL ? 0 : pa->val);
y= (pb == NULL ? 0 : pb->val);
sum = x + y + mod;
mod = sum / 10;
p->next = new ListNode(sum % 10);
p=p->next;
pa = (pa == NULL ? NULL : pa->next);//pa=pa->next;
pb = (pb == NULL ? NULL: pb->next);//pb=pb->next;
}
return head->next;
}
};
编辑于 2017-08-30 10:51:45
回复(0)
class Plus {
public:
ListNode* plusAB(ListNode* a, ListNode* b) {
if(!a || !b) return a?a:b;
ListNode* res=a,*apre;
int jin=0;
while(a && b){
int temp=a->val + b->val + jin;
a->val = temp%10;
jin = temp/10;
if(!a->next) apre=a;
a=a->next; b=b->next;
}
if(b) apre->next=b;
if(!a) a=b;
while(a){
int temp = a->val + jin;
a->val = temp%10;
jin=temp/10;
if(!a->next) apre=a;
a=a->next;
}
if(jin) apre->next = new ListNode(jin);
return res;
}
};
发表于 2017-08-17 21:58:52
回复(0)
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class Plus {
public:
ListNode* plusAB(ListNode* a, ListNode* b)
{
if(!a) return b;
if(!b) return a;
ListNode *L1 = new ListNode(0),*L2 = new ListNode(0);
L1->next = a,L2->next = b;
auto prep = L1,preq = L2,p = a,q = b;
int carry = 0;
while(p && q)
{
int sum = p->val + q->val + carry;
if(sum >= 10){sum -= 10;carry = 1;}
else carry = 0;
p->val = sum;
prep = p;
preq = q;
p = p->next;
q = q->next;
}
if(!p) {prep->next = q;p = q;}
while(p && carry + p->val == 10)
{
p->val = 0;
prep = p;
p = p->next;
}
if(!p && carry == 1)
{
ListNode* temp = new ListNode(1);
prep->next = temp;
}
else if(p && carry == 1)
++p->val;
return L1->next;
}
};
发表于 2017-06-29 15:36:44
回复(0)
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Plus {
public ListNode plusAB(ListNode a, ListNode b) {
return addListsHelper(a, b, 0);
}
public ListNode addListsHelper(ListNode a, ListNode b, int carry) {
if (a == null && b == null && carry == 0) {
return null;
}
int data = carry;
if (a != null) {
data += a.val;
}
if (b != null) {
data += b.val;
}
ListNode node = new ListNode(data % 10);
node.next = addListsHelper(a == null ? null : a.next,
b == null ? null : b.next,
data >= 10 ? 1 : 0);
return node;
}
}
发表于 2017-06-20 15:39:26
回复(0)
import java.util.*;
//自己太菜了，模仿别人做出来的，判断null很重要
public class Plus {
public ListNode plusAB(ListNode a, ListNode b) {
ListNode head =new ListNode(-1);
ListNode p =head;
if(a ==null){
return b;
}
if(b ==null){
return a;
}
int num =0;
while(a!=null||b!=null||num !=0){
int aval = a==null ? 0:a.val;
int bval = b==null ? 0:b.val;
int cval = aval+bval+num;
int sum =cval%10;
num =cval/10;
p.next =new ListNode(sum);
p=p.next;
a=a ==null?null:a.next;
b=b==null?null:b.next;
}
return head.next;
}
}
发表于 2017-05-16 23:55:15
回复(0)
//Java version for this question import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Plus { public ListNode plusAB(ListNode a, ListNode b) { ListNode p = new ListNode(-1); ListNode pHead = p; ListNode pNode = null; int sum = 0, c = 0, valA, valB; ListNode paNode = a, pbNode = b; while(paNode != null || pbNode != null || c != 0){ valA = (paNode == null ? 0 : paNode.val); valB = (pbNode == null ? 0 : pbNode.val); sum = valA + valB + c; c = sum / 10; pNode = new ListNode(sum % 10); p.next = pNode; p = p.next; paNode = (paNode == null ? null : paNode.next); pbNode = (pbNode == null ? null : pbNode.next); } p.next = null; return pHead.next; } }
编辑于 2017-05-01 11:47:16
回复(2)
/*@1.两个数位数一样多（每一位都面临进位）//@2.两数位数不一样多（A数比B数多出来的几位，是不面临进位的，而对 等的位数都面临进位）*/public class Plus { //首先定义全局头指针和位指针 ListNode head=null; ListNode tail=null; public ListNode plusAB(ListNode a, ListNode b) { // write code here //首先定义需要的变量 //进位标志 int flag=0; //首先分析两数长度一样的情况 while(a!=null&&b!=null){ insert((a.val+b.val+flag)%10); //将进位进行标记 flag=(a.val+b.val+flag)/10; a=a.next; b=b.next; } //如果A B两数同长，但最后发生了进位，则把进位装入新的一位，否则继续把进位加入下面情况 if(a==null&&b==null&flag!=0){ insert(flag); } //两数长度不一样的情况 if(a==null&&b!=null){ while(b!=null){ insert(b.val+flag); flag=(b.val+flag)/10; b=b.next; } } if(b==null&&a!=null){ while(a!=null){ insert(a.val+flag); flag=(a.val+flag)/10; a=a.next; } } return head; } public void insert(int result){ //首先创建一个新节点 ListNode node=new ListNode(result); if(head==null){ head=node; tail=node; }else{ tail.next=node; tail=node; } }
编辑于 2017-04-11 11:03:22
回复(0)
问题信息
难度：
149条回答
166收藏
35448浏览
通过挑战的用户
查看代码-
2022-10-13 15:58:05 -
2022-09-11 00:07:53
-
2022-09-06 14:47:20
-
2022-09-06 13:06:49
-
2022-09-05 10:58:36
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
class Plus { public: ListNode* plusAB(ListNode* a, ListNode* b) { // 头结点 ListNode *head = new ListNode(-1); ListNode *p = head; ListNode *node = nullptr; int c = 0,sum,val1,val2; ListNode *pa = a,*pb = b; //加法 while(pa != nullptr || pb != nullptr || c != 0){ val1 = (pa == nullptr ? 0 : pa->val); val2 = (pb == nullptr ? 0 : pb->val); sum = val1 + val2 + c; // 进位 c = sum / 10; node = new ListNode(sum % 10); //尾插法 p->next = node; p = node; pa = (pa == nullptr ? nullptr : pa->next); pb = (pb == nullptr ? nullptr : pb->next); }//while return head->next; } };