两个链表生成相加链表

解法一： 反转链表相加法

思路：先将两个链表进行反转，然后对应的值进行相加后生成新的链表，最后将链表再进行反转即得到结果！

import java.util.*;
public class Solution {
    public ListNode addInList (ListNode head1, ListNode head2) {
        head1 = reverse(head1);
        head2 = reverse(head2);
        ListNode newNode = new ListNode(-1);
        ListNode tmp = newNode;
        int add = 0;
        while(head1 != null || head2 != null){
            int val = add;
            if(head1 != null){
                val+=head1.val;
                head1 = head1.next;
            }
            if(head2 != null){
                val+=head2.val;
                head2 = head2.next;
            }
            tmp.next = new ListNode(val%10);
            add = val/10;
            tmp = tmp.next;
        }
        if(add > 0)
            tmp.next = new ListNode(add);
        return reverse(newNode.next);
    }
    public ListNode reverse(ListNode head){
        if(head == null) return head;
        ListNode tail = head;
        head = head.next;
        tail.next = null;
        while(head != null){
            ListNode temp = head.next;
            head.next = tail;
            tail = head;
            head = temp;
        }
        return tail;
    }
}

解法二：利用栈+头插法

思路： 利用栈先进先出的性质，分别将两个链表中从头往后遍历出所有的值存进去两个栈中，然后再分别从两个栈的栈顶取元素进行相加，有进位则保留，每次插入到链表的头部，最后要进行一次特判，判断此时的进位是否大于0，若大于0则需要将最后的这个进位插进去。

import java.util.*;
public class Solution {
    public ListNode addInList (ListNode head1, ListNode head2) {
        if(head1 == null) return head2;
        if(head2 == null) return head1;
        Stack<Integer> stack1 = initStack(head1);
        Stack<Integer> stack2 = initStack(head2);
        return initListNode(stack1,stack2);
    }
    public Stack initStack(ListNode head){
        Stack<Integer> stack = new Stack<>();
        while(head!=null){
            stack.add(head.val);
            head = head.next;
        }
        return stack;
    }
    public ListNode initListNode(Stack<Integer> stack1, Stack<Integer> stack2){
        ListNode head = null;
        int add = 0;
        while(!stack1.isEmpty() || !stack2.isEmpty()){
            int val1 = !stack1.isEmpty()?stack1.pop():0;
            int val2 = !stack2.isEmpty()?stack2.pop():0;
            int val = (val1+val2+add)%10;
            add = (val1+val2+add)/10;
            ListNode node = new ListNode(val);
            if(head == null){
                head = node;
            }else{
                node.next = head;
                head = node;
            }
        }
        if(add > 0){
            ListNode node = new ListNode(add);
            node.next = head;
            head = node;
        }
        return head;
    }
}