leetcode445.两数相加 II

1.题目描述：

给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字0之外，这两个数字都不会以零开头。

2.集合解法：

反向加往左进位我首先想到使用集合记录每个节点的val值然后使用工具类进行反转来解，硬着头皮改了好几次写下来，思路直接在代码中体现，推荐用栈。。。

class Solution {
    public ListNode addTwonumbers(ListNode l1, ListNode l2) {
        List list1 = new ArrayList<>();
        List list2 = new ArrayList<>();
        while(l1 != null){
            list1.add(l1.val);
            l1 = l1.next; 
        }
        while(l2 != null){
            list2.add(l2.val);
            l2 = l2.next;
        }//新建两个集合记录链表节点值
        Collections.reverse(list1);
        Collections.reverse(list2);
        for(int i = 0;i < Math.max(list1.size(),list2.size());i++){
           if(i < Math.min(list1.size(),list2.size())){
                list1.set(i,list1.get(i) + list2.get(i));
           }else if(list1.size() <= list2.size()){
                list1.add(list2.get(i));
           }
        }//list1记录相加后的节点值
        for(int i = 0;i < list1.size();i++){
            if(list1.get(i) >= 10){
                list1.set(i,list1.get(i) % 10);
                if(i == list1.size() - 1){
                    list1.add(1);
                }else{
                    list1.set(i + 1,list1.get(i + 1) + 1);
                }
            } 
        }//向右进一位，需要考虑最末值若为0则需向前增加一个1
        Collections.reverse(list1);//得到需要返回的链表对应的集合
        int j = 0;
        ListNode resNode = new ListNode(-1);
        ListNode temp = resNode;
        while(j < list1.size()){
            ListNode temp1 = new ListNode(list1.get(j++));
            temp.next = temp1;
            temp = temp.next; 
        }
        return resNode.next;//返回一个新链表
    }
}

3.栈解法：直接上代码了，简洁许多。

class Solution {
    public ListNode addTwonumbers(ListNode l1, ListNode l2) {
        Deque stack1 = new linkedList();
        Deque stack2 = new linkedList();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        int carry = 0;
        ListNode ans = null;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int a = stack1.isEmpty() ? 0 : stack1.pop();
            int b = stack2.isEmpty() ? 0 : stack2.pop();
            int cur = a + b + carry;
            carry = cur / 10;
            cur %= 10;
            ListNode curnode = new ListNode(cur);
            curnode.next = ans;
            ans = curnode;
        }
        return ans;
    }
}