将两个反向存储在链表中的整数求和（即整数的个位存放在了链表首部，一位数对应一个节点），返回的结果仍用链表形式。
给定两个链表ListNode* A，ListNode* B，请返回A+B的结果(ListNode*)。
测试样例：
{1,2,3},{3,2,1} 返回：{4,4,4}
[编程题]链式A+B
运行时间：21ms
占用内存：9996KB
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 n = a;
ListNode n1 = n;
while(a!=null && b!=null){
n.val = a.val+b.val;
if(n.val>=10){// 产生进位
if(a.next==null){ // 如果末尾为空新增一个节点
a.next=new ListNode(0);
}
a.next.val += n.val / 10;// 保存十位
n.val %= 10;// 保存个位
}
a=a.next;
b=b.next;
n=n.next;
}
return n1;
}
}
发表于 2020-10-28 10:19:41
回复(0)
public ListNode plusAB(ListNode a, ListNode b) {
//保存进位
int temp=0,ta=0;
//记录要返回的链表的头节点
ListNode head=a;
//模仿整数加法,如果其中一个链表走完，则剩下的链表只需拼接
while(a.next!=null&&b.next!=null) {
ta=a.val;
a.val=(temp+a.val+b.val)%10;
temp=(temp+ta+b.val)/10;
a=a.next;
b=b.next;
}
if (a.next==null) {
a.next=b.next;
}//把最后一个对齐的节点运算一下
ta=a.val;
a.val=(temp+a.val+b.val)%10;
temp=(temp+ta+b.val)/10;
//如果a b链表等长且有进位，则新增一节点
while(temp!=0){
if(a.next==null){
a.next=new ListNode(temp);
temp=0;
}else{//如果不等长但是有进位
a=a.next;
ta=a.val;
a.val=(a.val+temp)%10;
temp=(ta+temp)/10;
}
}
return head;
}
发表于 2020-06-18 16:16:33
回复(0)
public static ListNode plusAB(ListNode a, ListNode b) {
// write code here
ListNode c=new ListNode(-1);
ListNode root=c;
int count=0;
int sum=0;
while(a!=null&&b!=null) {
if(count!=0) {
sum=a.val+b.val+1;
}else {
sum=a.val+b.val;
}
count=sum/10;
sum=sum%10;
ListNode temp=new ListNode(sum);
c.next=temp;
c=c.next;
a=a.next;
b=b.next;
}
while (a!=null) {
if(count!=0) {
sum=a.val+1;
count=sum/10;
ListNode temp=new ListNode(sum%10);
c.next=temp;
c=c.next;
a=a.next;
}else {
ListNode temp=new ListNode(a.val);
c.next=temp;
c=c.next;
a=a.next;
}
}
while (b!=null) {
if(count!=0) {
sum=b.val+1;
count=sum/10;
ListNode temp=new ListNode(sum%10);
c.next=temp;
c=c.next;
b=b.next;
}else {
ListNode temp=new ListNode(b.val);
c.next=temp;
c=c.next;
b=b.next;
}
}
if(count!=0) {
c.next=new ListNode(count);
c=c.next;
c.next=null;
}
return root.next;
}
// write code here
ListNode c=new ListNode(-1);
ListNode root=c;
int count=0;
int sum=0;
while(a!=null&&b!=null) {
if(count!=0) {
sum=a.val+b.val+1;
}else {
sum=a.val+b.val;
}
count=sum/10;
sum=sum%10;
ListNode temp=new ListNode(sum);
c.next=temp;
c=c.next;
a=a.next;
b=b.next;
}
while (a!=null) {
if(count!=0) {
sum=a.val+1;
count=sum/10;
ListNode temp=new ListNode(sum%10);
c.next=temp;
c=c.next;
a=a.next;
}else {
ListNode temp=new ListNode(a.val);
c.next=temp;
c=c.next;
a=a.next;
}
}
while (b!=null) {
if(count!=0) {
sum=b.val+1;
count=sum/10;
ListNode temp=new ListNode(sum%10);
c.next=temp;
c=c.next;
b=b.next;
}else {
ListNode temp=new ListNode(b.val);
c.next=temp;
c=c.next;
b=b.next;
}
}
if(count!=0) {
c.next=new ListNode(count);
c=c.next;
c.next=null;
}
return root.next;
}
发表于 2020-03-22 13:58:42
回复(0)
Java实现，已通过。从个位开始带进位做加法，代码如下：
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 Head=null;
ListNode node=null;
int digit=0;
while (a!=null&&b!=null)
{
int current=a.val+b.val+digit;
if(current>=10)
{current=current%10;
digit=1;
}
else digit=0;
if(Head==null)
{Head=new ListNode(current);
node=Head;
}
else {node.next=new ListNode(current);
node=node.next;}
a=a.next;
b=b.next;
}
if(digit==0)
{
if(a==null&&b==null) return Head;
if (a==null)
{
node.next=b;
return Head;
}
if(b==null) node.next=a;
return Head;
// write code here
}
else
{
if(a==null&&b==null)
{
node.next=new ListNode(1);
return Head;
}
if(a==null)
{
while (b!=null)
{int val=digit+b.val;
if(val==10)
{ node.next=new ListNode(0);
digit=1;}
else {digit=0;
node.next=new ListNode(val);}
node=node.next;
b=b.next;
}
}
else
{
while (a!=null)
{int val=digit+a.val;
if(val==10)
{ node.next=new ListNode(0);
digit=1;}
else{ digit=0;
node.next=new ListNode(val);}
node=node.next;
a=a.next;
}
}
return Head;
}
}}
发表于 2020-02-26 14:48:51
回复(0)
最为直接的版本：全都往第二个链表中加
public class Plus {
public ListNode plusAB(ListNode a, ListNode b) {
ListNode ret = b;
while (a != null) {
b.val += a.val;
if (b.val >= 10) {
b.val %= 10;
if (b.next == null)
b.next = new ListNode(1);
else
b.next.val++;
}
if (b.next == null){
b.next = a.next;
break;
}
a = a.next;
b = b.next;
}
return ret;
}
} 递归：本省每个数相加为一个递归，进位又是另外一个递归
这个应该是最简洁最清晰版吧
public ListNode plusAB(ListNode a, ListNode b) {
if (a == null || b == null) return b == null ? a : b;
b.next = plusAB(a.next, b.next);
b.val += a.val;
addUp(b, b.next);
return b;
}
private void addUp(ListNode b, ListNode node) {
if (b.val >= 10) {
b.val %= 10;
if (node == null)
b.next = node = new ListNode(1);
else
node.val++;
addUp(node, node.next);
}
}
}
编辑于 2020-01-09 00:14:14
回复(0)
public class Plus {
public ListNode plusAB(ListNode a, ListNode b) {
int aValue = listNodeConvertIntValue(a);
int bValue = listNodeConvertIntValue(b);
int sumValue = aValue + bValue;
return intValueConvertListNode(sumValue);
}
private int listNodeConvertIntValue(ListNode node) {
StringBuilder *** = new StringBuilder();
ListNode curr = node;
while (curr != null) {
***.append(curr.val);
curr = curr.next;
}
return Integer.parseInt(***.reverse().toString());
}
private ListNode intValueConvertListNode(int value) {
char[] charArray = String.valueOf(value).toCharArray();
ListNode node = new ListNode(Integer.parseInt(String.valueOf(charArray[charArray.length - 1])));
ListNode cur = node;
for (int i = charArray.length - 2; i >= 0; i--) {
ListNode newNode = new ListNode(Integer.parseInt(String.valueOf(charArray[i])));
cur.next = newNode;
cur = newNode;
}
return node;
}
}
编辑于 2019-05-15 12:01:07
回复(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)
//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)
/*@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)
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) {
if (a == null && b == null) {
return null;
}
if (a == null) {
return b;
}
if (b == null) {
return a;
}
int lenA = getListLength(a);
int lenB = getListLength(b);
ListNode answerHead = null, answerTail = null, longer = null, shorter = null;
if (lenA >= lenB) {
longer = a;
shorter = b;
} else {
longer = b;
shorter = a;
}
answerHead = longer;
int sum = 0, carry = 0;
while (shorter != null) {
sum = longer.val + shorter.val + carry;
longer.val = sum % 10;
carry = sum / 10;
longer = longer.next;
shorter = shorter.next;
}
while (longer != null) {
sum = longer.val + carry;
longer.val = sum % 10;
carry = sum / 10;
longer = longer.next;
}
if (carry != 0) {
answerTail = answerHead;
while (answerTail.next != null) {
answerTail = answerTail.next;
}
ListNode node = new ListNode(carry);
answerTail.next = node;
}
return answerHead;
}
private int getListLength(ListNode head) {
int len = 0;
while (head != null) {
len++;
head = head.next;
}
return len;
}
}
发表于 2017-03-11 13:41:41
回复(0)
public static ListNode plusAB(ListNode a, ListNode b) {
int aLength=1,asum =0;
int bLength=1,bsum = 0;
int sum = 0;
ListNode list = new ListNode(0);
ListNode list2 =list;
ListNode listmid = new ListNode(-1);
while(a!=null){
asum+=a.val*aLength;
aLength*=10;
a = a.next;
}
while(b!=null){
bsum+=b.val*bLength;
bLength*=10;
b = b.next;
}
sum=asum+bsum;
//下面就是要将加起来的数字转成链表，想JB半天不会做。。。
int length = Integer.valueOf(sum).toString().length();
char[] array =
Integer.valueOf(sum).toString().toCharArray();
char chara ='0';
for(int i=array.length-1;i>=0;i--){
if(i==array.length-1){
list.val=array[i]-chara;
}else if(i==array.length-2){
list.next = new ListNode(array[i]-chara);
list2 = list;
list = list.next;
}else{
list.next = new ListNode(array[i]-chara);
list = list.next;
}
}
return list2;
}
方法有点笨，自己还想了好半天
发表于 2017-02-28 09:46: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 tmp = a;
int na=0,nb=0, i =0;
while (tmp != null){
na += tmp.val * Math.pow(10,i);
i++;
tmp = tmp.next;
}
tmp = b; i =0;
while (tmp != null){
nb += tmp.val * Math.pow(10,i);
i++;
tmp = tmp.next;
}
int sum = na + nb;
ListNode head = new ListNode(sum % 10);
tmp = head;
sum = sum/10;
while(sum != 0){
ListNode node = new ListNode(sum%10);
tmp.next = node;
tmp = node;
sum = sum/10;
}
return head;
}
}
发表于 2016-09-11 21:05:39
回复(0)
ListNode head = null;
int c = 0;
String s1 = "";
String s2 = "";
if(a == null || b ==null)
return null;
while(a != null )
{
s1 += a.val;
a = a.next;
}
while(b != null)
{
s2 += b.val;
b = b.next;
}
c = Integer.parseInt(ReseveString(s1))+ Integer.parseInt(ReseveString(s2));
String s = ReseveString(Integer.toString(c));
head = new ListNode(s.charAt(0)-48);
ListNode temp = head;
for(int i = 1 ;i < s.length();i++)
{
temp.next = new ListNode(s.charAt(i)-48);
temp = temp.next;
}
return head;
}
public String ReseveString(String str)
{
String s3 = "";
for(int i = str.length()-1;i>=0;i--)
{
s3 += str.charAt(i);
}
return s3;
}
发表于 2016-08-09 17:07:10
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：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; } };