题解 | #链表相加(二)#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        if(head1==null){
            return head2;
        }

        if(head2==null){
            return head1;
        }

    
        //创建两个栈
        Stack<ListNode> s1 = new Stack();

        Stack<ListNode> s2 = new Stack();

        Stack<ListNode>  resS = new Stack();

        while(head1!=null){
            s1.push(head1);
            head1 = head1.next;
        }

        while(head2!=null){
            s2.push(head2);
            head2 = head2.next;
        }

        //设置虚拟节点
        ListNode dummy = new ListNode(-1);

        ListNode pre = dummy;

        //进位的结果
        int cur = 0;

        while(!s1.isEmpty()||!s2.isEmpty()){
            int x = 0;
            if(!s1.isEmpty()){
                ListNode n1  = s1.pop();
                 x=(n1==null)?0:n1.val;
            }
           
            int y = 0;
            if(!s2.isEmpty()){
                ListNode n2  = s2.pop();
                 y=(n2==null)?0:n2.val;
            }

            int add = x+y+cur;

            //得到的结果
            int res = (add>=10)?add-10:add;
            //进位的结果
            cur = (add>=10)?1:0;

            ListNode temp = new ListNode(res);
            resS.push(temp);
        }

        if(cur!=0){
            ListNode temp = new ListNode(cur);
            resS.push(temp);
        }

        while(!resS.isEmpty()){
            pre.next = resS.pop();
            pre = pre.next;
        }
        return dummy.next;
    }
}