两个链表生成相加链表

1.暴力：将两个值用两个整数存起来，相加，再StringBuffer类型完成反正，再转换为字符串，最后存到结果链表中，时间复杂度：O（n），总体上还是一个循环；空间复杂度：O（1），但是会超过int类型的最大，而得不到正确结果
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;
int num1=0,num2=0;
ListNode p1=head1,p2=head2;
while(p1!=null){//得到第一个数
num1=num110+p1.val;
p1=p1.next;
}
while(p2!=null){//得到第二个数
num2=num2*10+p2.val;
p2=p2.next;
}
int sum=num1+num2;
StringBuffer sb=new StringBuffer();
while(sum!=0){
sb.append(sum%10);
sum/=10;
}
String str=sb.toString();
ListNode res=null;
for(int i=0;i<str.length();i++){//链接到结果链表
int n=str.charAt(i)-'0';
ListNode temp=new ListNode(n);
temp.next=res;
res=temp;
}
return res;
}
}
2.用两个栈利用先进后出的特点，栈不为空即出栈，为空即为0，完成两个数的相加，同时还需考虑进位，时间复杂度：O（n），空间复杂度：O（n）
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;
Stack<integer> s1=new Stack<>();
Stack<integer> s2=new Stack<>();
while(head1!=null){//存第一个数
s1.push(head1.val);
head1=head1.next;
}
while(head2!=null){//存第二个数
s2.push(head2.val);
head2=head2.next;
}
ListNode res=null;//结果链表
int cnt=0;
while(!s1.empty()||!s2.empty()){//进行相加
int num1=s1.isEmpty()?0:s1.pop();
int num2=s2.isEmpty()?0:s2.pop();
int sum=num1+num2+cnt;
cnt=sum/10;//当前的和是否需要进位
ListNode temp=new ListNode(sum%10);
temp.next=res;
res=temp;
}
if(cnt>0){//最后还有判断是否还有进位
ListNode temp=new ListNode(cnt);
temp.next=res;
res=temp;
}
return res;
}
}</integer></integer>