import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
/**
1.栈方法,LinkedList实现了栈的接口,可以当做栈使用,还能存储ListNode,不存在类型冲突
1.首先定义两个LinkedList,分别将数据存入其中
2.定义新的链表及相关辅助结点head,cur,定义进位
3一个个取出进行操作,循环条件为栈不为空,且进位不为0
4.移动链表,改变指针位置,实现新链表的输出并返回头结点,既最新结点
代码如下:
public class Solution {
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
public ListNode addInList (ListNode head1, ListNode head2) {
// write code here
//反转链表
LinkedList<Integer> stack1=new LinkedList<>();
LinkedList<Integer> stack2=new LinkedList<>();
//将链表放入栈中
ListNode a=head1;//定义辅助结点,遍历
ListNode b=head2;
while(a!=null){
stack1.push(a.val);
a=a.next;
}
while(b!=null){
stack2.push(b.val);
b=b.next;
}
int carry=0;//进位
ListNode head=null;
ListNode cur=null;
while(!stack1.isEmpty()||!stack2.isEmpty()||carry!=0){
int x=stack1.isEmpty()?0:stack1.pop();
int y=stack2.isEmpty()?0:stack2.pop();
int sum=x+y+carry;
carry=sum/10;//跟新进位
head=new ListNode(sum%10);
head.next=cur;
cur=head;//跟新结点位置,相当于从后往前加入结点
}
return head;
}
}
方法2:先逆序,再相加
1.定义一个逆序链表的函数,分别是实现链表的逆序
2.遍历链表,进行相加,条件依旧是链表不为空且进位不为0
3.反向添加结点,并返回;
代码如下:
import java.util.*;
public class Solution {
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
public ListNode addInList (ListNode head1, ListNode head2) {
// write code here
//反转两个链表
head1=reverseList(head1);
head2=reverseList(head2);
ListNode head=null;//添加表头
ListNode cur=null;//辅助遍历结点
int carry=0;
while(head1!=null||head2!=null||carry!=0){
int x=head1==null?0:head1.val;
int y=head2==null?0:head2.val;
int sum=x+y+carry;
carry=sum/10;
cur=new ListNode(sum%10);
cur.next=head;//反向添加结点
head=cur;
//移动链表
if(head1!=null){
head1=head1.next;
}
if(head2!=null){
head2=head2.next;
}
}
return cur;
}
//反转链表
public ListNode reverseList(ListNode pHead){
//定义一个表头
ListNode head=null;
ListNode cur=pHead;
while(cur!=null){
ListNode temp=cur.next;//保存下一结结点
cur.next=head;//反转链表
//更新结点位置
head=cur;
cur=temp;
}
return head;
}
}
*/
import java.util.*;
public class Solution {
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
public ListNode addInList (ListNode head1, ListNode head2) {
// write code here
//反转两个链表
head1=reverseList(head1);
head2=reverseList(head2);
ListNode head=null;//添加表头
ListNode cur=null;//辅助遍历结点
int carry=0;
while(head1!=null||head2!=null||carry!=0){
int x=head1==null?0:head1.val;
int y=head2==null?0:head2.val;
int sum=x+y+carry;
carry=sum/10;
cur=new ListNode(sum%10);
cur.next=head;//反向添加结点
head=cur;
//移动链表
if(head1!=null){
head1=head1.next;
}
if(head2!=null){
head2=head2.next;
}
}
return cur;
}
//反转链表
public ListNode reverseList(ListNode pHead){
//定义一个表头
ListNode head=null;
ListNode cur=pHead;
while(cur!=null){
ListNode temp=cur.next;//保存下一结结点
cur.next=head;//反转链表
//更新结点位置
head=cur;
cur=temp;
}
return head;
}
}