题解 | #两个链表生成相加链表#

反转链表或者栈的性质，栈结构真的好用！

import java.util.*;
public class Solution {
    //从后往前加，栈结构
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        Stack<ListNode> s1 = new Stack<>();
        Stack<ListNode> s2 = new Stack<>();
        int carry = 0;//进位

        while(head1!=null) {
            s1.push(head1);
            head1=head1.next;
        }

        while(head2!=null) {
            s2.push(head2);
            head2=head2.next;
        }

        while(!s1.isEmpty() || !s2.isEmpty() || carry!=0) {
            int x = s1.isEmpty() ? 0 : s1.pop().val;
            int y = s2.isEmpty() ? 0 : s2.pop().val;
            int sum = x + y + carry;
            carry = sum / 10;
            ListNode cur = new ListNode(sum%10);
            cur.next = head.next;
            head.next = cur;
        }
        return head.next;
}

结果用栈存储，计算结束后链接

import java.util.*;
public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    //从后往前加，栈结构
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        Stack<ListNode> s1 = new Stack<>();
        Stack<ListNode> s2 = new Stack<>();
        //栈存储结果，也可创建一个虚拟头结点，使用头插法；
        Stack<ListNode> res = new Stack<>();
        int carry = 0;//进位

        while(head1!=null) {
            s1.push(head1);
            head1=head1.next;
        }

        while(head2!=null) {
            s2.push(head2);
            head2=head2.next;
        }

        while(!s1.isEmpty() || !s2.isEmpty() || carry!=0) {
            int x = s1.isEmpty() ? 0 : s1.pop().val;
            int y = s2.isEmpty() ? 0 : s2.pop().val;
            int sum = x + y + carry;
            carry = sum / 10;
            res.push(new ListNode(sum%10));
        }
         ListNode head = res.isEmpty() ? null :res.pop(); 
         ListNode prev = head;
         while(!res.isEmpty()) {
             ListNode cur = res.pop();
             prev.next = cur;
             prev = prev.next;
         }
         return head;
    }
}