[数据结构与算法]Leetcode笔记----NC40 两个链表生成相加链表

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

思路1：也是我想到的思路，用两个数据结构存储链表各节点的值，在相加时从后往前加，每次相加的和大于10就减10再保留一个进位，这个数据结构其实就是栈，满足后进先出的规则，但我是用list实现的。
思路2：比较简单，其实思路1中我所做的就是把两个链表反转之后相加，既然如此先把两个链表反转再相加不就得了？根本用不到两个栈，节省了很多空间。

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        List<Integer> temp1 = new ArrayList<Integer>();
        List<Integer> temp2 = new ArrayList<Integer>();
        ListNode p1 = head1;
        ListNode p2 = head2;
        while(p1!=null&&p2!=null){
            temp1.add(p1.val);
            temp2.add(p2.val);
            p1 = p1.next;
            p2 = p2.next;
        }
        if(p1!=null){
            while(p1!=null){
                temp1.add(p1.val);
                p1 = p1.next;
            }
        }
        if(p2!=null){
            while(p2!=null){
                temp2.add(p2.val);
                p2 = p2.next;
            }
        }
        int loc1 = temp1.size()-1;
        int loc2 = temp2.size()-1;
        int jinwei = 0;
        ListNode temp = null;
        while(loc1>=0&&loc2>=0){
            int sum = temp1.get(loc1)+temp2.get(loc2)+jinwei;
            if(sum >= 10){
                sum -= 10;
                jinwei = 1;
            }
            else{jinwei = 0;}
            ListNode p = new ListNode(sum);
            p.next = temp;
            temp = p;
            loc1--;
            loc2--;
        }
        if(loc1>=0){
            for(int j = loc1;j>=0;j--){
                 int sum = jinwei+temp1.get(j);
                 if(sum >= 10){
                   sum -= 10;
                   jinwei = 1;
            }
            else{jinwei = 0;}
                 ListNode p = new ListNode(sum);
                 p.next = temp;
                 temp = p;
            }
        }
        if(loc2>=0){
            for(int j = loc2;j>=0;j--){
                 int sum = jinwei+temp2.get(j);
            if(sum >= 10){
                sum -= 10;
                jinwei = 1;
            }
            else{jinwei = 0;}
                 ListNode p = new ListNode(sum);
                 p.next = temp;
                 temp = p;
            }
        }
        if(jinwei == 1){
            ListNode p = new ListNode(1);
            p.next = temp;
            temp = p;}
        return temp;
    }
}