两个链表相加生成相加链表

思路
根据两个链表相加的特点，可以使用三个栈来模拟两个链表相加，第一个栈存第一个链表的头到尾节点，第二个链表存第二个链表的头到尾巴节点，由于节点值的进位是指向头节点，待前两个栈存完节点后取出相加，保留进位值，可以做到进位值随着栈的取出到达前一个节点，把前两个栈取出的值和进位值相加得到的值重新创一个ListNode节点存入第三个栈，当前两个栈都取空的时候，将第三个栈的节点循环取出重构链表即可得到结果，
代码

public ListNode addInList (ListNode head1, ListNode head2) {
    // write code here
    Stack<ListNode> stack1 = new Stack<>(); //存第一个链表的节点
    Stack<ListNode> stack2 = new Stack<>(); //存第二个链表的节点
    Stack<ListNode> stack3 = new Stack<>(); //存相加后链表的节点
    ListNode tail = new ListNode(0);        //初始化重构后的链表
    ListNode result = tail;                 //定义解为重构链表的头节点
    if (head1==null||head2==null){
        if (head1==null){
            return head2;
        }else {
            return head1;
        }
    }
    while (head1!=null){
        stack1.add(head1);
        head1=head1.next;
    }
    while (head2!=null){
        stack2.add(head2);
        head2=head2.next;
    }
    int val1=0;   //存第一个栈取出的值
    int val2=0;   //存第二个栈取出的值
    int sum =0;   //存val1,val2，next的和
    int next=0;   //定义进位值并初始化
    while (!stack1.empty()||!stack2.empty()){
        if (!stack1.empty()&&!stack2.empty()){
            val1=stack1.pop().val;
            val2=stack2.pop().val;
            sum=val1+val2+next;
            int val=sum%10;
            stack3.push(new ListNode(val));
            next=sum/10;
        }
        if (!stack1.empty()&&stack2.empty()){
            val1=stack1.pop().val;
            sum=val1+next;
            int val=sum%10;
            stack3.push(new ListNode(val));
            next=sum/10;
        }
        if (stack1.empty()&&!stack2.empty()){
            val2=stack2.pop().val;
            sum=val2+next;
            int val=sum%10;
            stack3.push(new ListNode(val));
            next=sum/10;
        }
    }
    while (!stack3.empty()){
        ListNode node=new ListNode(stack3.pop().val);
        tail.next=node;
        tail=tail.next;
    }
    return result.next;
}