假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
数据范围：
，链表任意值 
要求：空间复杂度)
，时间复杂度
要求：空间复杂度
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
[编程题]链表相加(二)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
public ListNode addInList (ListNode head1, ListNode head2) {
// write code here
ListNode head3=new ListNode(1);
ListNode pre=new ListNode(1);
ListNode head3temp=new ListNode(1);
head3temp=head3;
Stack<Integer> s1=new Stack<Integer>();
Stack<Integer> s2=new Stack<Integer>();
Stack<Integer> s3=new Stack<Integer>();
int b=0;
int val=0;
while(head1!=null)
{
s1.push(head1.val);
head1=head1.next;
}
while(head2!=null)
{
s2.push(head2.val);
head2=head2.next;
}
while(!s1.isEmpty()&&!s2.isEmpty())
{
val=s1.pop()+s2.pop()+b;
if(val>=10)
{
val=val-10;
b=1;
}
else
b=0;
s3.push(val);
}
while(!s1.isEmpty())
{
val=s1.pop()+b;
if(val>=10)
{
val=val-10;
b=1;
}
else
b=0;
s3.push(val);
}
while(!s2.isEmpty())
{
val=s2.pop()+b;
if(val>=10)
{
val=val-10;
b=1;
}
else
b=0;
s3.push(val);
}
while(!s3.isEmpty())
{
head3.val=s3.pop();
head3.next=new ListNode(0);
pre=head3;
head3=head3.next;
}
pre.next=null;
return head3temp;
}
}
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
public ListNode addInList (ListNode head1, ListNode head2) {
// write code here
ListNode head3=new ListNode(1);
ListNode pre=new ListNode(1);
ListNode head3temp=new ListNode(1);
head3temp=head3;
Stack<Integer> s1=new Stack<Integer>();
Stack<Integer> s2=new Stack<Integer>();
Stack<Integer> s3=new Stack<Integer>();
int b=0;
int val=0;
while(head1!=null)
{
s1.push(head1.val);
head1=head1.next;
}
while(head2!=null)
{
s2.push(head2.val);
head2=head2.next;
}
while(!s1.isEmpty()&&!s2.isEmpty())
{
val=s1.pop()+s2.pop()+b;
if(val>=10)
{
val=val-10;
b=1;
}
else
b=0;
s3.push(val);
}
while(!s1.isEmpty())
{
val=s1.pop()+b;
if(val>=10)
{
val=val-10;
b=1;
}
else
b=0;
s3.push(val);
}
while(!s2.isEmpty())
{
val=s2.pop()+b;
if(val>=10)
{
val=val-10;
b=1;
}
else
b=0;
s3.push(val);
}
while(!s3.isEmpty())
{
head3.val=s3.pop();
head3.next=new ListNode(0);
pre=head3;
head3=head3.next;
}
pre.next=null;
return head3temp;
}
}
发表于 2021-09-09 20:57:21
回复(0)
从链表尾部开始相加，可以利用栈的性质
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
ListNode* addInList(ListNode* head1, ListNode* head2) {
// write code here
if(head1 == NULL)
{
return head2;
}
if(head2 == NULL)
{
return head1;
}
stack<ListNode *> s1;
stack<ListNode *> s2;
while(head1 != NULL)
{
s1.push(head1);
head1 = head1->next;
}
while(head2 != NULL)
{
s2.push(head2);
head2 = head2->next;
}
int subsum = 0;
while(!s1.empty()||!s2.empty())
{
int sum = subsum;
if(!s1.empty())
{
sum += s1.top()->val;
head1 = s1.top();
s1.pop();
}
if(!s2.empty())
{
sum += s2.top()->val;
if(s2.size()>s1.size())
{
head1 = s2.top();
}
s2.pop();
}
if(sum < 10)
{
subsum = 0;
head1->val = sum;
}
else
{
subsum = sum/10;
head1->val = sum%10;
}
}
if(subsum > 0)
{
head2 = new ListNode(subsum);
head2->next = head1;
return head2;
}
return head1;
}
};
发表于 2020-08-26 16:27:08
回复(4)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
public ListNode addInList (ListNode head1, ListNode head2) {
// write code here
if(head1==null) return head2;
if(head2==null) return head1;
ListNode l1=reverse(head1);
ListNode l2=reverse(head2);
ListNode result=new ListNode(0);
int c=0;
while(l1!=null||l2!=null||c!=0)
{
int v1=l1!=null?l1.val:0;
int v2=l2!=null?l2.val:0;
int val=v1+v2+c;
c=val/10;
ListNode cur=new ListNode(val%10);
cur.next=result.next;
result.next=cur;
if(l1!=null)
l1=l1.next;
if(l2!=null)
l2=l2.next;
}
return result.next;
}
public ListNode reverse(ListNode node)
{
if(node==null) return node;
ListNode pre=null,next=null;
while(node!=null)
{
next=node.next;
node.next=pre;
pre=node;
node=next;
}
return pre;
}
} java没有答案 原来是java都过不掉 只能过过75%
发表于 2020-08-29 16:41:25
回复(8)
写一个比较容易让人看懂的解法：
1.链表从个位数加起，因此首先把两个链表逆序。
2.调整链表位数不齐，把两个链表的长度调整一致，短链表后面补0。
3.进行相加，设置一个下一位进位，每当当前位数超过10，设置进位为1，进位位参与运算过后立即置0。
4.将相加后的链表结果逆序返回。
运行结果：97% 88%
class Solution {
public:
ListNode* addInList(ListNode* head1, ListNode* head2) {
//1.逆序两个链表
ListNode* h1 = reverse(head1);
ListNode* h2 = reverse(head2);
//2.链表对齐补零
addZero(h1,h2);
//3.设置进位为并且相加
int nextAdd=0;
ListNode* head = h1;
int temp;
while(h1->next){
temp = h1->val+h2->val+nextAdd;//当前位就是两个链表的每一位与进位位相加
if(nextAdd==1)nextAdd=0;//进位位参与运算后置零
if(temp>=10){
h1->val=temp%10;//产生进位
nextAdd=1;
}
else h1->val = temp;
h1=h1->next;
h2=h2->next;
}
//最后一位单独运算，因为要考虑结果是否超过最大位数，超过最大位数，要新建链表扩容
temp = h1->val+h2->val+nextAdd;
if(temp>=10){
h1->val = temp%10;
h1->next = (ListNode*)malloc(sizeof(ListNode));
h1->next->val=1;
h1->next->next=NULL;
}
else h1->val=h1->val+h2->val+nextAdd;
return reverse(head);
}
void addZero(ListNode *h1,ListNode *h2){
while(h1->next&&h2->next){
h1=h1->next;
h2=h2->next;
}
//以下两个if只有一个会执行，短的补零
if(h1->next){
while(h1->next){
h2->next=(ListNode*)malloc(sizeof(ListNode));
h2->next->next=NULL;
h2->next->val=0;
h2=h2->next;
h1=h1->next;
}
}
if(h2->next){
while(h2->next){
h1->next=(ListNode*)malloc(sizeof(ListNode));
h1->next->next=NULL;
h1->next->val=0;
h1=h1->next;
h2=h2->next;
}
}
}
//链表逆序
ListNode * reverse(ListNode * list){
if(!list||!list->next)return list;
ListNode * p=list;
ListNode *head = list;
list=list->next;
p->next=NULL;
while(list){
head = list;
list=list->next;
head->next=p;
p=head;
}
return p;
}
};
发表于 2021-09-11 11:22:03
回复(1)
class Solution {
public:
ListNode* addInList(ListNode* head1, ListNode* head2) {
ListNode* newh1=nullptr;
ListNode* newh2=nullptr;
ListNode* p1=head1;
ListNode* p2=head2;
int len1=0,len2=0;
//翻转链表p1,p2，并记录链表长度
while(p1)
{
p1=head1->next;
head1->next=newh1;
newh1=head1;
head1=p1;
len1++;
}
while(p2)
{
p2=head2->next;
head2->next=newh2;
newh2=head2;
head2=p2;
len2++;
}
//令head1为长链表，后面相加结果直接在head1上改
if(len1<len2)
{
head1=newh2;
head2=newh1;
}
else
{
head1=newh1;
head2=newh2;
}
int carry=0;
p1=head1,p2=head2;
while(1)
{
//链表相加，短链表结束break
plus(p1,p2,carry);
if(!p2->next)
{
break;
}
p1=p1->next;
p2=p2->next;
}
//短链表的值已经全部计算过，注意将短链表的值置零（未置零出错过）
p2->val=0;
//还有进位就继续在长链表上相加，没进位长链表的值就不用修改了，直接返回长链表的头结点，省去了后面的无意义相加（比如长链表长度10000，短链表长度1，这样只用相加一两次）
while(carry)
{
if(!p1->next)
{
p1->next=new ListNode(1);
carry=0;
}
else
{
p1=p1->next;
plus(p1,p2,carry);
}
}
//将长链表翻转过来就是结果
p1=head1,newh1=nullptr;
while(p1)
{
p1=head1->next;
head1->next=newh1;
newh1=head1;
head1=p1;
}
return newh1;
}
//节点相加
void plus(ListNode* &p1, ListNode* &p2,int &carry)
{
p1->val=p1->val+p2->val+carry;
if(p1->val>9)
{
p1->val%=10;
carry=1;
}
else carry=0;
}
};
编辑于 2020-09-01 08:48:32
回复(0)
1先将链表分别存入栈中
2再从栈的末尾开始相加，记录进位值和当前结果
3使用头插法将结果存入结果链表中
class Solution: def addInList(self, head1, head2): # write code here if head1 == None: return head2 if head2 == None: return head1 '''存入栈''' s1, s2 = [], [] while head1: s1.append(head1.val) head1 = head1.next while head2: s2.append(head2.val) head2 = head2.next '''每次从栈末尾取出一个数进行相加，记录进位值并更新输出结果''' i = 0 # 进位值 temp = ListNode(0) # 链表尾部 while len(s1)>0 and len(s2)>0: num1 = int(s1.pop()) num2 = int(s2.pop()) node = ListNode((num1 + num2 + i)%10) # 当前结果 i = (num1 + num2 + i)//10 # 更新进位值 node.next = temp.next # 头插法，将新生成的数插入到当前链表的头部 temp.next = node '''处理其余特殊情况：s1先为空、s2先为空''' while len(s1)>0: num = int(s1.pop()) node = ListNode((num + i)%10) i = (num + i)//10 node.next = temp.next temp.next = node while len(s2)>0: num = int(s2.pop()) node = ListNode((num + i)%10) i = (num + i)//10 node.next = temp.next temp.next = node return temp.next
发表于 2021-07-24 14:32:08
回复(6)
链表相加
只有链表顺序是从个位开始，最高位结束时才可以相加（记录本位和进位，最后一位进位再新建一个节点即可）。如果链表顺序不是这样，则需要反转。
顺序不是从个位数开始，所以反转，然后加，然后结果再反转得到最后结果。
当p1或p2到头时候，就只加另一个。
进位c需要在里面加。
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
public ListNode addInList (ListNode head1, ListNode head2) {
// write code here
//先反转，然后再求和
ListNode p1 = reverse(head1);
ListNode p2 = reverse(head2);
//c为进位，a为当前位
ListNode root = new ListNode(-1), t;
t = root;
int c = 0, a = 0;
//p1和p2都不能为null
while(p1 != null && p2 != null){
//需要在里面加c
a = (p1.val + p2.val + c) % 10;
c = (p1.val + p2.val + c) / 10;
t.next = new ListNode(a);
t = t.next;
p1 = p1.next;
p2 = p2.next;
}
//分为一个为空，一个不为空（两种），两个都为空
while(p1 != null){
//需要在里面加c
a = (p1.val + c) % 10;
c = (p1.val + c) / 10;
t.next = new ListNode(a);
t = t.next;
p1 = p1.next;
}
while(p2 != null){
//需要在里面加c
a = (p2.val + c) % 10;
c = (p2.val + c) / 10;
t.next = new ListNode(a);
t = t.next;
p2 = p2.next;
}
if(c == 1){
t.next = new ListNode(1);
}
ListNode r = reverse(root.next);
return r;
}
public ListNode reverse(ListNode head){
ListNode a = head, c = null, b;
while(a != null){
b = a.next;
a.next = c;
c = a;
a = b;
}
return c;
}
}
发表于 2022-07-19 14:37:25
回复(0)
使用栈逆序链表节点，然后使用头插法。
import java.util.*;
public class Solution {
public ListNode addInList (ListNode head1, ListNode head2) {
Stack<ListNode> stack1=new Stack<>();
Stack<ListNode> stack2=new Stack<>();
ListNode p1=head1;
ListNode p2=head2;
while(p1!=null){
stack1.push(p1);
p1=p1.next;
}
while(p2!=null){
stack2.push(p2);
p2=p2.next;
}
int cause=0;
ListNode dummy=new ListNode(0);
ListNode p=dummy;
while(!stack1.isEmpty()||!stack2.isEmpty()){
int pp1=!stack1.isEmpty()?stack1.pop().val:0;
int pp2=!stack2.isEmpty()?stack2.pop().val:0;
int plus=cause+pp2+pp1;
cause=plus/10;
ListNode newNode=new ListNode(plus%10);
newNode.next=p.next;
p.next=newNode;
}
return dummy.next;
}
}
发表于 2020-10-31 14:41:33
回复(3)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
public ListNode addInList (ListNode head1, ListNode head2) {
head1 = reverse(head1);
head2 = reverse(head2);
ListNode res = new ListNode(-1), p = res;
int add = 0;//进位
while(head1 != null || head2 != null){
int a = head1 != null ? head1.val : 0;
int b = head2 != null ? head2.val : 0;
int re = add + a + b;
add = re >= 10 ? 1 : 0;
p.next = new ListNode(re % 10);
p = p.next;
if(head1 != null){
head1 = head1.next;
}
if(head2 != null){
head2 = head2.next;
}
}
if(add != 0){
p.next = new ListNode(1);
}
return reverse(res.next);
}
ListNode reverse(ListNode head){
ListNode newHead = null;
ListNode p = head;
while(p != null){
ListNode next = p.next;
p.next = newHead;
newHead = p;
p = next;
}
return newHead;
}
}
发表于 2021-08-08 19:45:49
回复(0)
Java：
/**
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
public ListNode addInList(ListNode head1, ListNode head2) {
//先翻转两个链表，然后逐位相加，有进位则加进位
ListNode r1 = reverse(head1);
ListNode r2 = reverse(head2);
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
int c = 0;
while (r1 != null || r2 != null) {
int d1 = r1 == null ? 0 : r1.val;
int d2 = r2 == null ? 0 : r2.val;
int sum = d1 + d2 + c;
cur.next = new ListNode(sum % 10);
c = sum / 10;
cur = cur.next;
r1 = r1 == null ? null : r1.next;
r2 = r2 == null ? null : r2.next;
}
//最后一位如有进位，则再单独加一个节点
if (c > 0) {
cur.next = new ListNode(c);
}
return reverse(dummy.next);
}
//翻转链表
public ListNode reverse(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode cur = head, pre = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
发表于 2021-02-10 17:31:33
回复(0)
//先反转链表，然后正常带进位的链表加法，最后把结果再反转
class Solution {
public:
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
ListNode* addInList(ListNode* head1, ListNode* head2) {
// write code here
ListNode* l1=reverse(head1);
ListNode* l2=reverse(head2);
int cur=0;
ListNode* head=new ListNode(-1);
ListNode* temp=head;
while(l1||l2||cur)
{
if(l1)
{
cur+=l1->val;
l1=l1->next;
}
if(l2)
{
cur+=l2->val;
l2=l2->next;
}
ListNode* t=new ListNode(cur%10);
temp->next=t;
temp=temp->next;
cur/=10;
}
temp->next=nullptr;
ListNode* ans=head->next;
return reverse(ans);
}
ListNode* reverse(ListNode* head) //反转链表
{
ListNode* pre=nullptr;
ListNode* cur=head;
while(cur!=nullptr)
{
ListNode* next=cur->next;
cur->next=pre;
pre=cur;
cur=next;
}
return pre;
}
};
发表于 2021-01-10 23:26:50
回复(0)
public class Solution {
public ListNode addInList (ListNode head1, ListNode head2) {
return reverseList(sumList(reverseList(head1), reverseList(head2)));
}
private ListNode reverseList(ListNode list) {
if (list == null || list.next == null) {
return list;
}
ListNode p = null;
ListNode q = list;
while (q != null) {
ListNode r = q.next;
q.next = p;
p = q;
q = r;
}
return p;
}
private ListNode sumList(ListNode list1, ListNode list2) {
ListNode dummyHead = new ListNode(0);
ListNode cur = dummyHead;
ListNode p = list1;
ListNode q = list2;
int carry = 0;
while (p != null || q != null) {
int val = (p == null ? 0 : p.val) + (q == null ? 0 : q.val) + carry;
carry = val / 10;
val = val % 10;
cur.next = new ListNode(val);
cur = cur.next;
p = p == null ? p : p.next;
q = q == null ? q : q.next;
}
if (carry != 0) {
cur.next = new ListNode(carry);
}
return dummyHead.next;
}
}
发表于 2024-09-18 12:14:37
回复(0)
class Solution {
public:
ListNode* reverseList(ListNode* head)
{
ListNode* cur = head;
ListNode* pre = nullptr;
while (cur)
{
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
ListNode* addInList(ListNode* head1, ListNode* head2) {
head1 = reverseList(head1);
head2 = reverseList(head2);
ListNode* dummy = new ListNode(-1); // 哨兵位
ListNode* cur = dummy;
int t = 0;
while (head1 || head2 || t)
{
if (head1) t += head1->val;
if (head2) t += head2->val;
cur->next = new ListNode(t % 10);
t /= 10;
cur = cur->next;
if (head1) head1 = head1->next;
if (head2) head2 = head2->next;
}
return reverseList(dummy->next);
}
};
发表于 2024-07-15 20:29:16
回复(0)
struct ListNode* ReverseList(struct ListNode* head ) {
struct ListNode *p,*res;
if((head==NULL) || (head->next==NULL))
return head;
p = head->next;
res = ReverseList(p);
p->next = head;
p->next->next = NULL;
return res;
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
struct ListNode *p,*p1,*p2,*res=NULL;
int carry=0;
p1 = ReverseList(head1);
p2 = ReverseList(head2);
while(p1!=NULL || p2!=NULL) {
int t;
t = (p1==NULL?0:p1->val)+(p2==NULL?0:p2->val)+carry;
if(t>9) {
carry = t/10;
t %= 10;
}
else
carry = 0;
if(res==NULL) {
res = (struct ListNode *)malloc(sizeof(struct ListNode));
res->val = t;
res->next = NULL;
p = res;
}
else {
struct ListNode *NewNode;
NewNode = (struct ListNode *)malloc(sizeof(struct ListNode));
NewNode->val = t;
NewNode->next = NULL;
p->next = NewNode;
p = p->next;
}
if(p1!=NULL)
p1 = p1->next;
if(p2!=NULL)
p2 = p2->next;
};
res = ReverseList(res);
return res;
}
编辑于 2024-03-15 18:01:27
回复(0)
一种比较传统的做法
typedef struct ListNode* pnode;
// 将两个链表的值求和
void mycombine(pnode head1,pnode head2,int len1,int len2){
pnode p=head1;
pnode q=head2;
while(len1>len2){
p=p->next;
len1--;
}//保持后对齐
while(p){
p->val+=q->val;
p=p->next;
q=q->next;
}
}
int carrybit(pnode head){ //实现进位操作
if(head==NULL)return 0;
head->val+=carrybit(head->next);
if(head->val>=10){
head->val-=10;
return 1;
}else return 0;
}
int mystrlen(pnode head){//计算链表得长度
int count=0;
while(head){
head=head->next;
count++;
}
return count;
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
if(head1==NULL) return head1;
if(head2==NULL) return head2;
int len1=mystrlen(head1);
int len2=mystrlen(head2);
pnode temp=NULL;
//找到较大的链表，求和得到的放入其中；
if(len1>=len2){
temp=head1;
mycombine(temp,head2,len1,len2);//两个链表的值加到temp里
}else{
temp=head2;
mycombine(temp,head1,len2,len1);//两个链表的值加到temp里
}
int i=carrybit(temp);
if(i==1){
pnode newhead=(pnode)malloc(sizeof(struct ListNode));
newhead->val=1;
newhead->next=temp;
temp=newhead;
}
return temp;
}
发表于 2022-11-25 23:09:02
回复(0)
利用栈
遍历连个链表,把节点的值分别放入两个栈中
然后在对两个栈进行出栈操作,相加,根据是不是大过10,判断要不要进位
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
public ListNode addInList (ListNode head1, ListNode head2) {
// write code here
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
//创建一个返回结果的链表
ListNode result = null;
//记录最大链表的
int index = 0;
while(head1 != null || head2 != null){
if(head1 != null){
ListNode temp = head1;
stack1.push(temp.val);
head1 = head1.next;
temp.next = null;
}
if(head2 != null){
ListNode temp = head2;
stack2.push(temp.val);
head2 = head2.next;
temp.next = null;
}
index++;
}
//记录进位
boolean j = false;
//进行出栈计算
while(index > 0){
Integer i1 = stack1.isEmpty()?0:stack1.pop();
Integer i2 = stack2.isEmpty()?0:stack2.pop();
//
Integer i3 = j?i1 + i2 + 1:i1 + i2;
if(i3 >= 10){
j = true;
//创建一个新节点
ListNode temp = new ListNode(i3%10);
temp.next =result;
result = temp;
}else{
j = false;
ListNode temp = new ListNode(i3);
temp.next =result;
result = temp;
}
index--;
}
if(j){
ListNode temp = new ListNode(1);
temp.next =result;
result = temp;
}
return result;
}
}
发表于 2022-05-01 19:14:19
回复(0)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
public ListNode addInList (ListNode head1, ListNode head2) {
// write code here
ListNode node1 = head1;
ListNode node2 = head2;
StringBuilder builder1 = new StringBuilder();
StringBuilder builder2 = new StringBuilder();
while (node1 != null) {
builder1.append(node1.val);
node1 = node1.next;
}
while (node2 != null) {
builder2.append(node2.val);
node2 = node2.next;
}
builder1.reverse();
String str1 = builder1.toString();
builder2.reverse();
String str2 = builder2.toString();
int f = 0;
StringBuilder res = new StringBuilder();
for (int i = 0; i < (str1.length() > str2.length() ? str1.length() : str2.length()); i++) {
int a = i < str1.length() ? Integer.parseInt(str1.charAt(i) + "") : 0;
int b = i < str2.length() ? Integer.parseInt(str2.charAt(i) + "") : 0;
int c = a + b + f;
res.append(c % 10);
f = c / 10;
}
if (f > 0) {
res.append(f);
}
res.reverse();
char[] ch = res.toString().toCharArray();
ListNode resNode = new ListNode(Integer.parseInt(ch[0] + ""));
ListNode node = resNode;
for (int i = 1; i < ch.length; i++) {
node.next = new ListNode(Integer.parseInt(ch[i] + ""));
node = node.next;
}
return resNode;
}
}
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
public ListNode addInList (ListNode head1, ListNode head2) {
// write code here
ListNode node1 = head1;
ListNode node2 = head2;
StringBuilder builder1 = new StringBuilder();
StringBuilder builder2 = new StringBuilder();
while (node1 != null) {
builder1.append(node1.val);
node1 = node1.next;
}
while (node2 != null) {
builder2.append(node2.val);
node2 = node2.next;
}
builder1.reverse();
String str1 = builder1.toString();
builder2.reverse();
String str2 = builder2.toString();
int f = 0;
StringBuilder res = new StringBuilder();
for (int i = 0; i < (str1.length() > str2.length() ? str1.length() : str2.length()); i++) {
int a = i < str1.length() ? Integer.parseInt(str1.charAt(i) + "") : 0;
int b = i < str2.length() ? Integer.parseInt(str2.charAt(i) + "") : 0;
int c = a + b + f;
res.append(c % 10);
f = c / 10;
}
if (f > 0) {
res.append(f);
}
res.reverse();
char[] ch = res.toString().toCharArray();
ListNode resNode = new ListNode(Integer.parseInt(ch[0] + ""));
ListNode node = resNode;
for (int i = 1; i < ch.length; i++) {
node.next = new ListNode(Integer.parseInt(ch[i] + ""));
node = node.next;
}
return resNode;
}
}
发表于 2022-04-20 10:15:05
回复(0)
// 使用栈暂存一下，然后逐步计算，记得进位就好
public ListNode addInList (ListNode head1, ListNode head2) {
ArrayDeque<Integer> s1 = new ArrayDeque<>();
ArrayDeque<Integer> s2 = new ArrayDeque<>();
while (head1 != null) {
s1.push(head1.val);
head1 = head1.next;
}
while (head2 != null) {
s2.push(head2.val);
head2 = head2.next;
}
int carry = 0, val = 0;
ListNode res = null;
while (!s1.isEmpty() || ! s2.isEmpty() || carry != 0) {
val = carry;
if (!s1.isEmpty()) val += s1.pop();
if (!s2.isEmpty()) val += s2.pop();
carry = val / 10;
val %= 10;
ListNode node = new ListNode(val);
node.next = res;
res = node;
}
return res;
}
发表于 2021-12-29 12:51:17
回复(1)
问题信息
难度：
525条回答
1186收藏
14656浏览
通过挑战的用户
查看代码-
2023-03-08 10:33:10 -
2023-02-04 19:27:02
-
2023-01-30 11:11:51
-
2023-01-20 01:16:08 -
2022-12-24 16:12:23
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
