题解 | 链表相加(二)

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 || head2 == null)
        return null;

        //定义2个新栈
        Deque<Integer> l1 = new ArrayDeque();
        Deque<Integer> l2 = new ArrayDeque();

        //把两个链表分别压入两个栈
        pushAll(l1, head1);
        pushAll(l2, head2);

        //进位
        int carry = 0;
        //新链表储存值
        ListNode res = null;

        //加法运算
        while(!l1.isEmpty() || !l2.isEmpty() || carry != 0){
            int x = (!l1.isEmpty()) ? l1.pop() : 0;
            int y = (!l2.isEmpty()) ? l2.pop() : 0;
            int sum = x + y + carry;
            carry = sum / 10;

            ListNode node = new ListNode(sum % 10);
            node.next = res; //头插法
            res = node;
        }
        return res;
    }

    public void pushAll(Deque<Integer> stack, ListNode head){
        while(head != null){
            stack.push(head.val);
            head = head.next;
        }
    }
}