使用两个栈来实现链表加法

首先考虑两个数字相加之后结果的长度只有两种情况，假设n1 + n2 = res，n1 的长度是 l1, n2 的长度是 l2，res 的长度只可能为两种情况，case1：max(l1, l2)，比如123+456=579; case2: max(l1, l2)+1，比如1+999=1000。基于上述分析，可得出总体思路如下：
1、使用两个栈结构存储链表数据，根据栈的特性，弹出的顺序挣好就是从个位开始到高位的顺序。
2、根据栈的长度可以分别确定两个链表的长度，即两个数的位数。
3、编写addCore(Stack<listnode> s1, Stack<listnode> s2)方法，此时通过上层调用处的处理，可以确保s1的长度是大于s2的长度的，相加之后的结果保存在s1弹出的节点中，即在原来较长的链表中直接修改数值位结果值。最后如果inc==1，也就是说全部相加之后还有进位，意味着长度要+1，所以创建新节点，并指向上次弹出的节点，并返回该节点，否则直接返回上次弹出的节点。</listnode></listnode>

public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if(head1==null || head2==null){
            return head1==null ? head2 : head1;
        }
        Stack<ListNode> s1 = new Stack<>();
        Stack<ListNode> s2 = new Stack<>();
        ListNode n1 = head1, n2 = head2;

        while(n1!=null){
            s1.push(n1);
            n1 = n1.next;
        }
        while(n2!=null){
            s2.push(n2);
            n2 = n2.next;
        }
        return s1.size()>s2.size() ? addCore(s1, s2) : addCore(s2, s1);
    }
    private ListNode addCore(Stack<ListNode> s1, Stack<ListNode> s2){
        int inc = 0, ans = 0;
        ListNode t = null;
        while(s1.size()!=0 && s2.size()!=0){
            t = s1.pop();
            ans = t.val + s2.pop().val + inc;
            inc = ans>=10 ? 1 : 0;
            t.val = ans % 10;
        }
        while(s1.size()!=0){
            t = s1.pop();
            ans = t.val + inc;
            inc = ans>=10 ? 1 : 0;
            t.val = ans % 10;
        }
        if(inc==1){
            ListNode head = new ListNode(inc);
            head.next = t;
            return head;
        }
        return t;
    }