[数据结构与算法]剑指 Offer II 025. 链表中的两数相加

翻转list也可以，不过太麻烦了。

注意一个点，在出栈的时候建立链表的方式是尾插法，我们先从最尾部开始，首先让res结点指向null，然后建立新节点指向res，res再重新定位向该结点，继续建立下个新节点指向res……以此类推。

这样，最终res指向的便是这个链表的表头。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> stack1 = new ArrayDeque<>();
        Deque<Integer> stack2 = new ArrayDeque<>();
        
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null){
            stack2.push(l2.val);
            l2 = l2.next;
        }
        ListNode ans = null;
        int bit = 0;
        //进位完成……
        while(!stack1.isEmpty() || !stack2.isEmpty() ){
            int sum = 0;
            if (!stack1.isEmpty()){
                sum = sum + stack1.pop();
            } 
            if (!stack2.isEmpty()){
                sum = sum + stack2.pop();
            }
            sum = sum + bit;
            ListNode temp = new ListNode(sum%10);
            bit = sum/10;
            temp.next = ans;
            ans = temp;
        }//注意这个链表是通过尾插法建立的
        //先有ans 然后制造新节点指向ans ans=新节点
        //然后继续制造新节点 如此循环

        if(bit>0){
            ListNode temp = new ListNode(bit);
            temp.next = ans;
            ans = temp;
        }
        return ans;
        

    } 
}