题解 | 链表相加(二)

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if(head1==null) return head2;
        if(head2==null) return head1;

        Deque<Integer> s1 = new ArrayDeque<>();
        Deque<Integer> s2 = new ArrayDeque<>();

        //将链表元素压入栈中
        for(ListNode a = head1; a!=null; a=a.next) s1.push(a.val);
        for(ListNode b = head2; b!=null; b=b.next) s2.push(b.val);

        int carry = 0;
        ListNode head = null;
        while(!s1.isEmpty() || !s2.isEmpty() || carry != 0){//注意这里的carry！！
            int x = (s1.isEmpty())?0:s1.pop();
            int y = (s2.isEmpty())?0:s2.pop();
            int sum = x+y+carry;
            carry = sum/10;
            ListNode node = new ListNode(sum%10);
            node.next = head;//头插法
            head = node;
        }
        return head;
    }
}