445. Add Two Numbers II

让你求链表的和，这里有个follow up要求你不改变链表，那么可以使用stack，在这里我使用了三个stack两个用来存储值，一个用来存储node，发现跑出来的代码比别人慢了20ms左右，原来别人的第三个stack存的也是val，然后在pop过程中新建node。这里确实是一个优化的点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = storeToStack(l1);
        Stack<Integer> stack2 = storeToStack(l2);
        int carry = 0;
        Stack<ListNode> stack = new Stack<ListNode>();
        while(!stack1.isEmpty()&&!stack2.isEmpty())
        {
            int val1 = stack1.pop();
            int val2 =stack2.pop() ;
            int remain = (val1+val2+carry)%10;
            carry =(val1+val2+carry)/10;
            ListNode temp = new ListNode (remain); 
            stack.push(temp);
            
        }
        if(!stack1.isEmpty())
        {
             while(!stack1.isEmpty())
             {
            int val1 = stack1.pop();
            int remain = (val1+carry)%10;
            carry =(val1+carry)/10;
            ListNode temp = new ListNode (remain); 
            stack.push(temp);
             }
        }
        if(!stack2.isEmpty())
        {
            while(!stack2.isEmpty())
            {
            int val2 =stack2.pop() ;
            int remain = (val2+carry)%10;
            carry =(val2+carry)/10;
            ListNode temp = new ListNode (remain); 
            stack.push(temp);
            }
            
        }
        if(carry==1)
        {
            ListNode temp = new ListNode (1); 
            stack.push(temp);
        }
        ListNode dummy = new ListNode (0);
        ListNode pos =dummy;
        while(!stack.isEmpty())
        {
            pos.next=stack.pop();
            pos=pos.next;
        }
        return dummy.next;
    }
    // return a stack stores the number of listnode
    private Stack<Integer> storeToStack(ListNode head)
    {
        Stack<Integer> stack = new Stack<>();
        while(head!=null)
        {
            stack.push(head.val);
            head=head.next;
        }
        return stack;
    }
}