让你求链表的和，这里有个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;
}
}
