给定两个用链表表示的整数，每一个节点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。 示例 输入：(7-1-6) (5-9-2), 即 617 295. 输出：2-1-9, 即912. 进阶 假设这些数位是正向存放的，请
给定两个用链表表示的整数，每一个节点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。
示例
输入：(7->1->6) + (5->9->2), 即 617 + 295.
输出：2->1->9, 即912.
进阶
假设这些数位是正向存放的，请再做一遍。
示例
输入：(6->1->7) + (2->9->5), 即617 + 295.
输出：9->1->2, 即912.
**进阶的解法告诉我们，涉及单链表逆序的问题，可以借助栈来解决。
package test;
import java.util.Stack;
public class AddLinkedInt {
//两个整数反向存放
//即，个位排在链表的首部
public Node addLinkedInt(Node l1, Node l2){
Node newHead = new Node(0);
Node tail = newHead;
int carry = 0;
Node p1 = l1, p2 = l2;
while(p1!=null || p2!=null){
int val1 = (p1==null)? 0 : p1.val;
int val2 = (p2==null)? 0 : p2.val;
int val = (val1+val2+carry)%10;
carry = (val1+val2+carry)/10;
tail.next = new Node(val);
tail = tail.next;
}
if(carry != 0)
tail.next = new Node(carry);
return newHead.next;
}
//两个整数正向存放
//即，个位排在链表的末尾
public Node addLinkedInt(Node l1, Node l2){
//这里要借助栈来处理
Stack st1 = new Stack();
Stack st2 = new Stack();
Node p1=l1, p2=l2;
//将两链表的数据分别压入栈中
while(p1 != null){
st1.push(p1.val);
p1 = p1.next;
}
while(p2 != null){
st2.push(p2.val);
p2 = p2.next;
}
//将结果相加入栈
Stack res = new Stack();
int carry=0;
while( !st1.empty() || !st2.empty()){
int val1 = st1.empty() ? 0 : st1.pop();
int val2 = st2.empty() ? 0 : st2.pop();
res.push((val1+val2+carry)%10);
carry = (val1+val2+carry)/10;
}
if(carry != 0)//注意进位的处理
res.push(carry);
Node newHead = new Node(0);
Node tail = newHead;
while(!res.empty()){
tail.next = new Node(res.pop());
tail = tail.next;
}
return newHead.next;
}
}