题解 | #两个链表生成相加链表#

将两个链表中的元素存入两个栈；
对两个栈中的元素进行出栈相加，放入第三个栈；
最后判断哪一个栈非空，将栈中的元素存入第三个栈，注意判断此时的进位carry是否为0；
之后将栈中的元素出栈，构建链表；

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
        //两个链表入栈之后，相加入第三个栈
        Stack<Integer> stack1=new Stack<>();
        Stack<Integer> stack2=new Stack<>();
        ListNode p1=head1;
        ListNode p2=head2;
        while(p1!=null){
            stack1.push(p1.val);
            p1=p1.next;
        }
        while(p2!=null){
            stack2.push(p2.val);
            p2=p2.next;
        }
        int carry=0;
        Stack<Integer> stack3=new Stack<>();
        while(!stack1.empty()&&!stack2.empty()){
            int tem=carry+stack1.pop()+stack2.pop();
            stack3.push(tem%10);
            carry=tem/10;
        }
        while(!stack1.empty()){
            int tem=stack1.pop()+carry;
            stack3.push(tem%10);
            carry=tem/10;
        }
        while(!stack2.empty()){
            int tem=stack2.pop()+carry;
            stack3.push(tem%10);
            carry=tem/10;
        }
        if(carry!=0)
            stack3.push(carry);
        ListNode p3=head1;
        //连接两个链表
        while(p3.next!=null){
            p3=p3.next;
        }
        p3.next=head2;
        ListNode p4=head1;
        while(!stack3.empty()){
            p4.val=stack3.pop();
            if(stack3.empty())
                continue;
            else//当栈为空时，指针再移动
                p4=p4.next;
        }
        p4.next=null;
        return head1;
    }
}