CCI2.5链表整数求和

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;	
	}
}