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

方法：先用栈来实现倒序，然后创建新链表

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while (head1 != null || head2 != null) {
            if (head1 != null) {
                stack1.add(head1.val);
                head1 = head1.next;
            }
            if (head2 != null) {
                stack2.add(head2.val);
                head2 = head2.next;
            }
        }

        ListNode newHead = new ListNode(-1);    //虚拟头节点
        int carry = 0;

        //这里设置carry!=0,是因为当st1,st2都遍历完时，如果carry=0,就不需要进入循环了
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int a = 0, b = 0;
            if (!stack1.isEmpty()) a = stack1.pop();
            if (!stack2.isEmpty()) b = stack2.pop();
            int sum = a + b + carry;    //每次的和应该是对应位相加再加上进位
            ListNode cur = new ListNode(sum % 10);    //对累加的结果取余
            //头插法（每次都插入最开始的位置，避免顺序打乱）
            cur.next = newHead.next;
            newHead.next = cur;
            carry = sum / 10;    //看是否有进位
        }
        return newHead.next;
    }
}