链表相加

题目描述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

思路

使用栈来存储链表中的节点，之后同时出栈，就可以让个位数对着个位数，十位数对着十位数。
然后使用第三个栈来存储数据。第三个栈在第一个栈和第二栈出栈的时候把出栈的节点的和新建为一个节点添加到第三个栈中。
因为可能会出现进位的情况，所以使用一个进位的标识，如果jinwei = true就需要进位，如果为false就不需要进位。
因为数据最大是9+9所以进位只能出现+1的情况。
在最终创建新链表的头结点的时候判断是否需要进位，如果进位就新建一个头结点，如果不需要进位就把第三个栈的pop的数据指定为头结点。
然后连接链表。

    public ListNode addInList (ListNode head1, ListNode head2) {
        //直接让对应的链表相加使用栈
        Stack<ListNode> s1 = new Stack<>();
        Stack<ListNode> s2 = new Stack<>();
        Stack<ListNode> s3 = new Stack<>();

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

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

        boolean jinwei = false;

        while(s1.size() > 0 && s2.size() > 0) {
            int sum = s1.pop().val + s2.pop().val;
            if(jinwei){
                sum ++;
            }

            if(sum > 9){
                sum -=10;
                jinwei = true;
            }else {
                jinwei = false;
            }
            s3.add(new ListNode(sum));
        }

        while(s1.size()>0){
            int sum = s1.pop().val;
            if(jinwei){
                sum ++;
            }
            if(sum > 9){
                sum -=10;
                jinwei = true;
            }else {
                jinwei = false;
            }
            s3.add(new ListNode(sum));
        }

        while(s2.size()>0){
            int sum = s2.pop().val;
            if(jinwei){
                sum ++;
            }
            if(sum > 9){
                sum -=10;
                jinwei = true;
            }else {
                jinwei = false;
            }
            s3.add(new ListNode(sum));
        }
        ListNode head;
        if(jinwei){
            head = new ListNode(1);
        }else {
            head = s3.pop();
        }
        ListNode temp = head;
        while(s3.size() > 0){
            temp.next = s3.pop();
            temp = temp.next;
        }

        return head;
    }